Lower bounds for off-line range searching |
| |
Authors: | B Chazelle |
| |
Institution: | (1) Department of Computer Science, Princeton University, NJ 08544 Princeton, USA |
| |
Abstract: | This paper proves three lower bounds for variants of the following rangesearching problem: Given n weighted points inR
d
andn axis-parallel boxes, compute the sum of the weights within each box: (1) if both additions and subtractions are allowed,
we prove that Ω(n log logn) is a lower bound on the number of arithmetic operations; (2) if subtractions are disallowed the lower bound becomes Ω(n(logn/loglogn)d-1), which is nearly optimal; (3) finally, for the case where boxes are replaced by simplices, we establish a quasi-optimal
lower bound of Ω(n2-2/(d+1))/polylog(n).
A preliminary version of this paper appeared inProc. 27th Ann. ACM Symp. on Theory of Computing, May 1995, pp. 733–740. This work was supported in part by NSF Grant CCR-93-01254 and the Geometry Center, University of
Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|