I don't want to reinvent the wheel and I want to see what algorithms are out there for my perusal. I'd prefer original published papers if you've got links like that.
Optimal Partitioning for Efficient I/O in Spatial Databases
"It is desirable to design partitioning techniques that minimize the I/O time incurred during query execution in spatial databases. In this paper, we explore optimal partitioning techniques for spatial data for different types of queries, and develop multi-disk allocation techniques that maximize the degree of I/O parallelism obtained during the retrieval. We show that hexagonal partitioning has optimal I/O cost for circular queries compared to all possible non-overlapping partitioning techniques that use convex regions. For rectangular queries, we show that although for the special case when queries are rectilinear, rectangular grid partitioning gives superior performance, hexagonal partitioning has overall better I/O cost for a general class of range queries. We then discuss parallel storage and retrieval techniques for hexagonal partitioning using current techniques for rectangular grid partitioning."
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8...