Quasi-optimal range searching in spaces of finite VC-dimension

Bernard Chazelle, Emo Welzl

Research output: Contribution to journalArticle

121 Scopus citations

Abstract

The range-searching problems that allow efficient partition trees are characterized as those defined by range spaces of finite Vapnik-Chervonenkis dimension. More generally, these problems are shown to be the only ones that admit linear-size solutions with sublinear query time in the arithmetic model. The proof rests on a characterization of spanning trees with a low stabbing number. We use probabilistic arguments to treat the general case, but we are able to use geometric techniques to handle the most common range-searching problems, such as simplex and spherical range search. We prove that any set of n points in Ed admits a spanning tree which cannot be cut by any hyperplane (or hypersphere) through more than roughly n1-1/d edges. This result yields quasi-optimal solutions to simplex range searching in the arithmetic model of computation. We also look at polygon, disk, and tetrahedron range searching on a random access machine. Given n points in E2, we derive a data structure of size O(n log n) for counting how many points fall inside a query convex k-gon (for arbitrary values of k). The query time is O(√kn log n). If k is fixed once and for all (as in triangular range searching), then the storage requirement drops to O(n). We also describe an O(n log n)-size data structure for counting how many points fall inside a query circle in O(√n log2n) query time. Finally, we present an O(n log n)-size data structure for counting how many points fall inside a query tetrahedron in 3-space in O(n2/3 log2n) query time. All the algorithms are optimal within polylogarithmic factors. In all cases, the preprocessing can be done in polynomial time. Furthermore, the algorithms can also handle reporting within the same complexity (adding the size of the output as a linear term to the query time).

Original languageEnglish (US)
Pages (from-to)467-489
Number of pages23
JournalDiscrete & Computational Geometry
Volume4
Issue number1
DOIs
StatePublished - Dec 1 1989

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Quasi-optimal range searching in spaces of finite VC-dimension'. Together they form a unique fingerprint.

  • Cite this