alt Hacker NewsWhy would someone select "quad" trees in particular, instead of binary splitting at each level (in alternating dimensions; something like a K-D tree)? I.e., what are the tradeoffs? The article briefly mentions K-D trees at the very end, but doesn't elaborate on differences:
> The quadtree is the two-dimensional case of a broader family of space-partitioning data structures. Octrees extend the same idea to three dimensions (splitting cubes into eight children), KD-trees use alternating axis-aligned splits (splitting along x, then y, then x again), and R-trees group nearby objects into bounding rectangles. Each variant makes different tradeoffs between construction time, query speed, and update cost.
Finally, I'll add: the presentation is very high quality and served as a great introduction of the concept.
Replies
KD-trees select their splits according to the contained points. That tends to make them better for static sets of points, but updates become expensive. Quadtrees are often used in e.g. physics engines.
Not commenting on the quad tree specifically but I know a lot of reasoning that goes into non-binary tree structures comes down to performance gains from exploiting cache entry size. When each node lookup in the tree is going to trigger an 64-byte load from L1, it's often much better performance to have your tree have 4 or 8 pointers to children in that cache entry rather than two if it means you do on average half or quarter as many traversals.