| Invented by | Jon Louis Bentley (1975) | |
| Idea: |
- a search tree for points of a \(k\)-dimensional space, built by comparing one coordinate at a time
- the points sit in the leaves; every internal node is a single line — an axis and a value, copied from one of the points below it — cutting the region the node inherited into the two regions its children inherit
- which axis a node cuts on alternates with depth: e.g. in 2D it's x, then y, then x again
- the tree is therefore both a search tree and a subdivision of space: a subtree is a rectangle, and knowing that rectangle is what lets a query skip the subtree whole
|
| Advantages: |
- a range query costs \(O(\sqrt n + t)\) in 2D to report \(t\) points, since regions falling entirely inside the query are reported without being examined
- a nearest-neighbour query costs \(O(\log n)\) on well-spread points and \(O(\sqrt n)\) in 2D in the worst case, since the search visits only the regions its current circle reaches into
- \(O(n)\) space
|
| Disadvantages: |
- shape depends on insertion order — a bad order degrades queries to a scan
- the pruning weakens as \(k\), the number of dimensions, grows; in high dimensions range queries and nearest-neighbour search end up visiting nearly everything
|