For range searching and nearest neighbor respectively in 2d area, which one of quad tree and kd tree is better?

Question

Suppose all the data isn’t dynamic, for range searching and nearest neighbor respectively, which one of Kd tree and quad tree is often preferred?

The time complexity without rebalancing should be the same. Then What’s exact difference between the two data structures when performing searching operations?

Answer 1

You're asking two questions related to 2D static tree structures.

1) What's the structure difference between the 2 trees.

I think the main differences are as follows:

• A KdTree can have 2 children for each node and and a quad tree 4.
• A KdTree supports multiple splitting techniques for subdividing the space. One such splitting technique could make the tessellation generated by both trees identical, in which case the KdTree would be twice the height. Another technique such as the median split would results in a balanced tree. In this case the height of the KdTree could be less than that of the QuadTree depending on the point distribution. This is because a QuadTree always splits in 4 identical quadrants.

2) Which tree is better (what's the performance difference between the 2 trees).

This is difficult to answer, because realistically, this very much depends on the implementation quality or for which purpose they were implemented. As such, different implementations of just the same structure can already have large performance differences.

Since you are interested in range and nearest neighbor searches, Wikipedia states that (point) QuadTrees have been surpassed by KdTrees.