@inproceedings{794d01668f204567a2d06056187cbb79,
title = "Quasi-optimal upper bounds for simplex range searching and new zone theorems",
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.",
author = "Bernard Chazelle and Micha Sharir and Emo Welzl",
year = "1990",
doi = "10.1145/98524.98532",
language = "English (US)",
isbn = "0897913620",
series = "Proc Sixth Annu Symp Comput Geom",
publisher = "Publ by ACM",
pages = "23--33",
booktitle = "Proc Sixth Annu Symp Comput Geom",
note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",
}