Quasi-optimal upper bounds for simplex range searching and new zone theorems

Bernard Chazelle, Micha Sharir, Emo Welzl

Research output: Contribution to journalArticlepeer-review

70 Scopus citations

Abstract

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a set P of n points in ℜd so that, given any query simplex q, the points in P ∩q can be counted or reported efficiently. If m units of storage are available (n <m <nd), then we show that it is possible to answer any query in O(n1+e{open}/m1/d) query time after O(m1+e{open}) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieve O(log n) query time at the expense of O(nd+e{open}) storage for any fixed e{open} > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.

Original languageEnglish (US)
Pages (from-to)407-429
Number of pages23
JournalAlgorithmica
Volume8
Issue number1
DOIs
StatePublished - Jan 1 1992

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design
  • Software
  • Safety, Risk, Reliability and Quality
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Quasi-optimal upper bounds for simplex range searching and new zone theorems'. Together they form a unique fingerprint.

Cite this