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 -