Halfspace range search: An algorithmic application of k-sets

Bernard Chazelle, F. P. Preparata

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


Given a fixed set S of n points in E3 and a query plane π, the halfspace range search problem asks for the retrieval of all points of S on a chosen side of π. We prove that with O(n(log n)8 (loglog n)4) storage it is possible to solve this problem in O(k+log n) time, where k is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number of j-sets (j=1, ..., k) realized by a set of n points in E3 is O(nk5); a k-set is any subset of S of size k which can be separated from the rest of S by a plane.

Original languageEnglish (US)
Pages (from-to)83-93
Number of pages11
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Halfspace range search: An algorithmic application of k-sets'. Together they form a unique fingerprint.

Cite this