Tree::R looks great for learning about one might implement an R-Tree in pure Perl. If I was looking for something to actually use I'd probably prefer something that provides an interface to an existing robust, fast C implementation. If you create one, let us know!

-sam