Difference between quadtree and kd-tree

Question

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 1

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.