30

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.

Asif Rehan
  • 983
  • 2
  • 8
  • 25
Mauricio Galindo
  • 638
  • 1
  • 10
  • 16
  • See also http://cstheory.stackexchange.com/questions/8470/why-would-one-ever-use-an-octree-over-a-kd-tree – naught101 Mar 21 '14 at 04:57

1 Answers1

31

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.

killogre
  • 1,730
  • 15
  • 26
  • 2
    Careful: kd-trees also scale exponentially in the number of dimensions. The main difference is kd-trees end up deeper but narrower. – Apollys supports Monica Dec 27 '18 at 01:46
  • How is the depth related to the number of dimensions? Isn't the depth $\log(N)$? – Eduardo Reis May 27 '20 at 05:02
  • 1
    @EduardoReis In the d-dimensional version of quadtree, the width is exponential in the depth. The depth log(N) only if the the data is balanced, which is unlikely. – killogre Jun 03 '20 at 09:41