Abstract
We give a lower bound on the following problem, known as
simplex range reporting: Given a collection
P of
n points in
d-space and an arbitrary simplex
q, find all the points in
P ∩
q. It is understood that
P is fixed and can be preprocessed ahead of time, while
q is a query that must be answered on-line. We consider data structures for this problem that can be modeled on a pointer machine and whose query time is bounded by
O(
n
δ
+
r), where
r is the number of points to be reported and δ is an arbitrary fixed real. We prove that any such data structure of that form must occupy storage
Ω(n
d(1 − δ)− ε)
, for any fixed
ε > 0. This lower bound is tight within a factor of
n
ε
.
