×

How hard is half-space range searching? (English) Zbl 0778.68087

Summary: We investigate the complexity of half-space range searching: given \(n\) points in \(d\)-space, build a data structure that allows us to determine efficiently how many points lie in a query half-space. We establish a tradeoff between the storage \(m\) and the worst-case query time \(t\) in the Fredman/Yao arithmetic model of computation. We show that \(t\) must be at least on the order of \[ (n/\log n)^{1-(d-1)/d(d+1)}/m^{1/d}. \] Although the bound is unlikely to be optimal, it falls reasonably close to the recent upper bound of \(O(n/m^{1/d})\) established by Matouŝek. We also show that it is possible to devise a sequence of \(n\) inserts and half-space range queries that require a total time of \(n^{2-O(1/d)}\). Our results imply the first nontrivial lower bounds for spherical range searching in any fixed dimension. For example, they show that, with linear storage, circular range queries in the plane require \(\Omega(n^{1/3})\) time (modulo a logarithmic factor).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Agarwal, P. K., Sharir, M. Applications of a new partitioning scheme,Discrete Comput. Geom.9 (1993), 13-38. · Zbl 0773.68065 · doi:10.1007/BF02189304
[2] Barany, I., Larman, D. Convex bodies, economic cap coverings, random polytopes,Mathematika35 (1988), 274-291. · Zbl 0674.52003 · doi:10.1112/S0025579300015266
[3] Burkhard, W. A., Fredman, M. L., Kleitman, D. J. Inherent complexity trade-offs for range query problems,Theoret. Comput. Sci.16 (1981), 279-290. · Zbl 0522.68090 · doi:10.1016/0304-3975(81)90099-2
[4] Chazelle, B. Lower bounds on the complexity of polytope range searching,J. Amer. Math. Soc.2 (1989), 637-666. · Zbl 0695.68032 · doi:10.1090/S0894-0347-1989-1001852-0
[5] Chazelle, B. Lower bounds for orthogonal range searching: I. The reporting case,J. Assoc. Comput. Mach.37 (1990), 200-212. · Zbl 0696.68051 · doi:10.1145/77600.77614
[6] Chazelle, B. Lower bounds for orthogonal range searching: II. The arithmetic model,J. Assoc. Comput. Mach.37 (1990), 439-463. · Zbl 0699.68058 · doi:10.1145/79147.79149
[7] Chazelle, B., Rosenberg, B. The complexity of computing partial sums off-line,Internat. J. Comput. Geom. Applic.1 (1991), 33-45. · Zbl 0724.68047 · doi:10.1142/S0218195991000049
[8] Chazelle, B.; Rosenberg, B., Lower bounds on the complexity of simplex range reporting on a pointer machine, No. 623, 439-449 (1992), Berlin · Zbl 1425.68430
[9] Chazelle, B., Sharir, M., Welzl, E. Quasi-optimal upper bounds for simplex range searching and new zone theorems,Algorithmica8 (1992), 407-429. · Zbl 0788.68141 · doi:10.1007/BF01758854
[10] Chazelle, B., Welzl, E. Quasi-optimal range searching in spaces of finiteVC-dimension,Discrete Comput. Geom.4 (1989), 467-489. · Zbl 0681.68081 · doi:10.1007/BF02187743
[11] Clarkson, K., Shor, P. Applications of random sampling to computational geometry, II,Discrete Comput. Geom.4 (1989), 387-421. · Zbl 0681.68060 · doi:10.1007/BF02187740
[12] Cole, R., Yap, C. K. Geometric retrieval problems,Inform. Control63 (1984), 39-57. · Zbl 0591.68091 · doi:10.1016/S0019-9958(84)80040-6
[13] Edelsbrunner, H., Welzl, E. Halfplanar range search in linear space andO(n0.695) query time,Inform. Process. Lett.23 (1986), 289-293. · Zbl 0634.68064 · doi:10.1016/0020-0190(86)90088-8
[14] Ewald, G., Larman, D.G., Rogers, C.A. The directions of the line segments and of ther-dimensional balls on the boundary of a convex body in Euclidean space,Mathematika17 (1970), 1-20. · Zbl 0199.57002 · doi:10.1112/S0025579300002655
[15] Fredman, M. L. A lower bound on the complexity of orthogonal range queries,J. Assoc. Comput. Mach.28 (1981), 696-705. · Zbl 0468.68049 · doi:10.1145/322276.322281
[16] Fredman, M. L. Lower bounds on the complexity of some optimal data structures,SIAM J. Comput.10 (1981), 1-10. · Zbl 0454.68006 · doi:10.1137/0210001
[17] Groemer, H. On the mean value of the volume of a random polytope in a convex set,Arch. Math.25 (1974), 86-90. · Zbl 0287.52009 · doi:10.1007/BF01238645
[18] Grotschel, M., Lovasz, L., Schrijver, A.Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988. · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4
[19] Haussler, D., Welzl, E. Epsilon-nets and simplex range queries,Discrete Comput. Geom.2 (1987), 127-151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[20] Macbeath, A. M. A theorem on non-homogeneous lattices,Ann. of Math. (2)56, (1952), 269-293. · Zbl 0047.04903 · doi:10.2307/1969800
[21] Matoušek, J. Reporting points in halfspaces,Proc. 32nd Ann. Symp. Found. Comput. Sci., 1991, pp. 207-215.
[22] Matoušek, J. Range searching with effient hierarchical cuttings,Proc. 8th Ann. ACM Symp. Comput. Geom., 1992, pp. 276-285.
[23] Mehlhorn, K.Data Structures and Algorithms 3: Multidimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984. · Zbl 0556.68003 · doi:10.1007/978-3-642-69900-9
[24] Santaló, L. A.Integral Geometry and Geometric Probability, Encyclopedia of Mathematics and Its Applications, Vol. 1 (Gian-Carlo Rota, ed.), Addison-Wesley, Reading, MA, 1976. · Zbl 0342.53049
[25] Spencer, J.Ten Lectures on the Probablistic Method, CBMS-NSF, SIAM, Philadelphia, PA, 1987. · Zbl 0703.05046
[26] Willard, D. E. Polygon retrieval,SIAM J. Comput.11 (1982), 149-165. · Zbl 0478.68060 · doi:10.1137/0211012
[27] Yao, F. F. A 3-space partition and its applications,Proc. 15th Ann. ACM Symp. Theory Comput., 1983, pp. 258-263.
[28] Yao, A. C. On the complexity of maintaining partial sums,SIAM J. Comput.14 (1985), 277-288. · Zbl 0564.68072 · doi:10.1137/0214022
[29] Yao, A. C., Yao, F. F. A general approach tod-dimensional geometric queries,Proc. 17th Ann. ACM Symp. Theory Comput., 1985, pp. 163-168.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.