Pre RTree step: Divide a set of points into rectangular regions each containing one point

Question

given my current position (lat,long) I want to quickly find the nearest neighbor in a points of interest problem. Thus I intend to use an R-Tree database, which allows for quick lookup. However, first the database must be populated - of course. Therefore, I need to determine the rectangular regions that covers the area, where each region contains one point of interest.

My question is how do I preprocess the data, i.e. how do I subdivide the area into these rectangular sub-regions? (I want rectangular regions because they are easily added to the RTree - in contrast to more general Voronoi regions).

/John

Answer 1

Edit: The below approach works, but ignores the critical feature of R-trees -- that The splitting behavior of R-tree nodes is well defined, and maintains a balanced tree (through B-tree-like properties). So in fact, all you have to do is:

1. Pick the maximum number of rectangles per page
2. Create seed rectangles (use points furthest away from each other, centroids, whatever).
3. For each point, choose a rectangle to put it into
   4. If it already falls into a single rectangle, put it in there
   5. If it does not, extend the rectangle that needs to be extended least (different ways to measure "least" exits -- area works)
   6. If multiple rectangles apply -- choose one based on how full it is, or some other heuristic
4. If overflow occurs -- use the quadratic split to move things around...
5. And so on, using R-tree algorithms straight out of a text book.

I think the method below is ok for finding your initial seed rectangles; but you don't want to populate your whole R-tree that way. Doing the splits and rebalancing all the time can be a bit expensive, so you will probably want to do a decent chunk of the work with the KD approach below; just not all of the work.

---

The KD approach: enclose everything in a rectangle.

If the number of points in the rectangle is > threshold, sweep in direction D until you cover half the points.

Divide into rectangles left and right (or above and below) the splitting point).

Call the same procedure recursively on the new rectangles, with the next direction (if you were going left to right, you will now go top to bottom, and vice versa).

The advantage this has over the divide-into-squares approach offered by another poster is that it accommodates skewed point distributions better.

Answer 2

Oracle Spatial Cartridge documentation describes tessellation algorithm that can do what you want. In short:

• enclose all your points in square
• if square contains 1 point - index square
• if square does not contain points - ignore it
• if square contains more then 1 point
  • split square into 4 equal squares and repeat analysis for each new square

Result should be something like this:
alt text http://download-uk.oracle.com/docs/cd/A64702_01/doc/cartridg.805/a53264/sdo_ina5.gif