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

Abstract

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
Pages23-33
Number of pages11
ISBN (Print)0897913620, 9780897913621
DOIs
StatePublished - Jan 1 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

Conference

ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA
Period6/6/906/8/90

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this