Random sampling, halfspace range reporting, and construction of (≤k)-levels in three dimensions

Research output: Contribution to journalConference articlepeer-review

Abstract

Given n points in three dimensions, we show how to answer halfspace range reporting queries in O(log n+k) expected time for an output size k. Our data structure can be preprocessed in optimal O(n log n) expected time. We apply this result to obtain the first optimal randomized algorithm for the construction of the (≤k)-level in an arrangement of n planes in three dimensions. The algorithm runs in O(n log n+nk2) expected time. Our techniques are based on random sampling. Applications in two dimensions include an improved data structure for `k nearest neighbors' queries, and an algorithm that constructs the order-k Voronoi diagram in O(n log n+nk log k) expected time.

Original languageEnglish (US)
Pages (from-to)586-594
Number of pages9
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1998
Externally publishedYes
EventProceedings of the 1998 39th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 8 1998Nov 11 1998

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Random sampling, halfspace range reporting, and construction of (≤k)-levels in three dimensions'. Together they form a unique fingerprint.

Cite this