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

Bernard Chazelle, Micha Sharir, Emo Welzl

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

22 Scopus citations


We consider the following problem, known as simplex range searching: Preprocess a set P of n points in Rd so that, given any query simplex q, the points in P intersection q can be counted or reported efficiently. We can put the many variants of this problem under the same umbrella by assuming a weight function on the points and asking for the cumulative weight of the points in P intersection q. For the sake of generality, it is best to disallow the use of subtraction (which will make our upper bounds more powerful): formally, this means choosing weights in an additive semigroup. The main topics are simplex range searching in polylogarithmic time, trading off storage and query time, and an improved theorem for planes in three dimensions.

Original languageEnglish (US)
Title of host publicationProc Sixth Annu Symp Comput Geom
PublisherPubl by ACM
Number of pages11
ISBN (Print)0897913620, 9780897913621
StatePublished - 1990
EventProceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA
Duration: Jun 6 1990Jun 8 1990

Publication series

NameProc Sixth Annu Symp Comput Geom


ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA

All Science Journal Classification (ASJC) codes

  • General Engineering

Cite this