Menu
What is the main difference between a quadtree and kd-tree? I understand they split points in many dimensions, but I do not understand why we would use one over the other. I need a structure that allows me to count how many points (2D points) are in a given region. Basically, I am trying to detect clusters of points.
885
For polygons: The search time in the quad-kd tree is reduced by 71.4% compared to quad-tree and 55.6% compared to kd-tree. For points and polygons from a GIS map: The search time in the quad-kd tree is reduced by 67.47% compared to kd-tree and 51.3% compared to quad-tree.
A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions.
In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space.
KD-trees are a specific data structure for efficiently representing our data. In particular, KD-trees helps organize and partition the data points based on specific conditions.
The difference (algorithmically) is: in quadtrees, the data reaching a node is split into a fixed (2^d), equal size cells, whereas in kdtrees, the data is split into two regions based on some data analysis (e.g. the median of some coordinate). Quadtrees do not scale well to high dimensions, due to the exponential dependency in the dimension. The data structures also differ in their query time complexities.
Since you're interested in 2D points, either data structure may work for you. KD trees are very easy to query for ranges, and are generally preferred over quadtrees. I suggest you use them.
200
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
