Optimal halfspace range reporting in three dimensions

Peyman Afshani, Timothy M. Chan

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

Abstract

We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that n points in 3-d can be stored in a linear-space data structure so that all k points inside a query halfspace can be reported in O(log n + k) time. The data structure can be built in O(n log n) expected time. The previous methods with optimal query time required superlinear (O(n log log n)) space. We also mention consequences, for example, to higher dimensions and to external-memory data structures. As an aside, we partially answer another open question concerning the crossing number in Matoušek's shallow partition theorem in the 3-d case (a tool used in many known halfspace range reporting methods).

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Pages180-186
Number of pages7
ISBN (Print)9780898716801
DOIs
StatePublished - 2009
Externally publishedYes
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew York, NY
Period1/4/091/6/09

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Optimal halfspace range reporting in three dimensions'. Together they form a unique fingerprint.

Cite this