Optimal Partition Trees

Research output: Contribution to journalArticlepeer-review


We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157-182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n 1-1/d) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n 1+ε) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315-334, 1992) requires O(nlog n) preprocessing time but O(n 1-1/dlog O(1)n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n 1-1/d) query time with high probability. Our method has several advantages: •It is conceptually simpler than Matoušek's O(n 1-1/d)-time method. Our partition trees satisfy many ideal properties (e. g., constant degree, optimal crossing number at almost all layers, and disjointness of the children's cells at each node). • It leads to more efficient multilevel partition trees, which are needed in many data structuring applications (each level adds at most one logarithmic factor to the space and query bounds, better than in all previous methods). • A similar improvement applies to a shallow version of partition trees, yielding O(nlogn) time, O(n) space, and O(n 1-1/[d/2]) query time for halfspace range emptiness in even dimensions d≥4. Numerous consequences follow (e. g., improved results for computing spanning trees with low crossing number, ray shooting among line segments, intersection searching, exact nearest neighbor search, linear programming queries, finding extreme points,...).

Original languageEnglish (US)
Pages (from-to)661-690
Number of pages30
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - Jun 2012
Externally publishedYes


  • Geometric data structures
  • Halfspace range searching
  • Simplex range searching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Optimal Partition Trees'. Together they form a unique fingerprint.

Cite this