Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Say I have 2 permutations of the the same set of elements. I create 2 R-Trees, one for each permutation.
Do I end up with 2 structurally identical R-Trees or not?
PS: My elements are rectangles on a plane.
Reformulation of the question: is there an insertion algorithm that reconstructs the same R-Tree regardless of the order of elements in use?
the R tree algorithms typically create "R"s (rectangles) iteratively/sequentially based on the order of insertion of the data. the "R"s are built directly out of the coordinates of the data seen so far. it does not appear that there are widely studied R-tree variants that build identical trees no matter what the order is, it does not seem to be a generally desired design criteria for the algorithms, which are judged on other criteria such as performance of search, insertion, overflow splitting etc.
except in artificial/contrived/"pathological" cases, the resulting R-trees will be "close" in structure and performance no matter what order the insertion. however it is not inconceivable that such an algorithm could be devised with the property of "resultant tree invariance" based on adjusting the insertion and overflow splitting logic.
on the other hand if you dont require an online algorithm you could just sort your data according to any criteria beforehand and the R tree will end up with the same structure of course.
a close alternative that can be adjusted to have the "order invariant" property you describe is the Quadtree because it is based on partitioning the overall space (assuming its dimensions are known) in a fractal "4-square" pattern that does not depend on ordering of the input or directly use the individual points for bounding coordinates.
