TY - GEN
T1 - POLYTOPE RANGE SEARCHING AND INTEGRAL GEOMETRY.
AU - Chazelle, Bernard
PY - 1987
Y1 - 1987
N2 - A family of lower bounds on the space-time complexity of simplex range searching is established. It is proved that the worst-case query time is OMEGA (n/ ROOT m), for d equals 2, and more generally, OMEGA (n/log n)/ m**1**/**d), for d greater than equivalent to 3; n is the number of points and m is the amount of storage available. These bounds hold with high probability for a random point-set (from a uniform distribution) and thus are valid in the worst case as well as on the average. They still hold if the query remains congruent to a fixed simplex or even a fixed slab.
AB - A family of lower bounds on the space-time complexity of simplex range searching is established. It is proved that the worst-case query time is OMEGA (n/ ROOT m), for d equals 2, and more generally, OMEGA (n/log n)/ m**1**/**d), for d greater than equivalent to 3; n is the number of points and m is the amount of storage available. These bounds hold with high probability for a random point-set (from a uniform distribution) and thus are valid in the worst case as well as on the average. They still hold if the query remains congruent to a fixed simplex or even a fixed slab.
UR - http://www.scopus.com/inward/record.url?scp=0023560074&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023560074&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1987.48
DO - 10.1109/sfcs.1987.48
M3 - Conference contribution
AN - SCOPUS:0023560074
SN - 0818608072
SN - 9780818608070
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 1
EP - 10
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -