Difference between quadtree and kd-tree

computational-geometry kdtree quadtree
Mauricio Galindo picture Mauricio Galindo · Nov 21, 2012 · Viewed 11.2k times · Source

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.

Answer

killogre picture killogre · Nov 26, 2012

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.

Related questions

How to determine if a list of polygon points are in clockwise order?

Having a list of points, how do I find if they are in clockwise order? For example: point[0] = (5,0) point[1] = (6,4) point[2] = (4,5) point[3] = (1,5) point[4] = (1,0) would say that it is anti-clockwise (or counter-clockwise, for some people).

Read More
An algorithm for inflating/deflating (offsetting, buffering) polygons

How would I "inflate" a polygon? That is, I want to do something similar to this: The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the …

Read More
Sort points in clockwise order?

Given an array of x,y points, how do I sort the points of this array in clockwise order (around their overall average center point)? My goal is to pass the points to a line-creation function to end up with …

Read More