Splitting and merging R-Trees.

[bigeasy]

Considering how to split and merge leafs in an R-Tree. A partition will divide a rectangle in two, but how to merge rectangles when they might not be exactly next to each other? You can split not by creating a two rectangles each with a different area, but one rectangle that is contained by what was the full rectangle. Then the smaller rectangle goes first. You test by scanning from left to right. To merge you must find a rectangle that can fit inside another rectangle, but someone will always be able to fit into the left most rectangle.