Halfspace range search: An algorithmic application of K-sets

Bernard Chazelle, Franco P. Preparata

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Given a fixed set S of n points in E∗ and a query plane the halfspace range search problem asks for the retrieval of all points of 5 on a chosen side of x. We prove that with 0(n(logn)8(loglogn)4) storage it is posAsible to solve this problem ia 0(k 4- logn) time, where k is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the maximum number of Ar-sets realized by a set of n points in E is 0(nfce) for a small positive constant c; a fc-set is any subset of S of size k which can be separated from the rest of S by a plane. Incidentally, this result constitutes the only nontrivial upper bound, as a function of n and k, known to date.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PublisherAssociation for Computing Machinery, Inc
Pages107-115
Number of pages9
ISBN (Electronic)0897911636, 9780897911634
DOIs
StatePublished - Jun 1 1985
Externally publishedYes
Event1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States
Duration: Jun 5 1985Jun 7 1985

Publication series

NameProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

Other

Other1st Annual Symposium on Computational Geometry, SCG 1985
CountryUnited States
CityBaltimore
Period6/5/856/7/85

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Geometry and Topology

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

  • Cite this

    Chazelle, B., & Preparata, F. P. (1985). Halfspace range search: An algorithmic application of K-sets. In Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 (pp. 107-115). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323248