Lower bounds on the complexity of polytope range searching. (English) Zbl 0695.68032

The range search problem of size (n,p) is specified by a set P of n points in Euclidean d-space and a collection Q of subsets \(q\subseteq {\mathbb{R}}^ d\), called queries, with \(| \{P\cap q:\) \(q\in Q\}| =p\). Here Q may be the set of all hyperrectangles, simplices, balls in Euclidean d-space, etc. Suppose we are given m units of computer memory. The problem is to organize the memory to be a position to answer the following questions efficiently: Given an arbitrary query \(q\in Q\), how many of the n points lie inside q? The author proves a family of lower bounds on the space-time complexity of the range search problem where Q is a collection of simplices or slabs.
First, it is proved that any range search problem of size (n,p) may be solved within \(t=O(n/\log_ 2(p/n))\) query time and \(m=O(p/\log_ 2(p/n))\) memory cells. Surprisingly, this result is in fact optimal: there exists a constant \(c>0\) and a class of search problems of size (n,p) that require \(m=\Omega (p)\) memory cells to be solved in query time \(t\leq cn/\log_ 2(p/n).\)
Second, it is proved that simplex range searching on n points requires \(\omega\) (n/\(\sqrt{m})\) query time in two dimensions and \(\Omega ((n/\log_ 2n)/m^{1/d})\) query time in any dimension \(d\geq 3.\)
These bounds hold for a random point-set with high probability, and thus are valid in the worst case as well as on the average. Interestingly, they still hold if the queries are restricted to congruent copies of a fixed simplex or even a fixed slab. The paper also contains several results of independent interest regarding to bipartite Ramsey theory and an intriguing generalization of Heilbornn’s problem: Given two integers n and \(k\leq n\), place n points in a unit square so that the convex hull of any k of them has an area at least \(\Omega\) (k/n). It is shown that this can be done if k exceeds \(\log_ 2n\).
Reviewer: S.P.Yukna


68Q25 Analysis of algorithms and problem complexity
52Bxx Polytopes and polyhedra
68U99 Computing methodologies and applications
Full Text: DOI


[1] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions, Dover, New York, 1970. · Zbl 0171.38503
[2] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0326.68005
[3] Walter A. Burkhard, Michael L. Fredman, and Daniel J. Kleitman, Inherent complexity trade-offs for range query problems, Theoret. Comput. Sci. 16 (1981), no. 3, 279 – 290. · Zbl 0522.68090 · doi:10.1016/0304-3975(81)90099-2
[4] B. Chazelle, Lower bounds on the complexity of multidimensional searching, Proc. 27th Annual IEEE Sympos. on Foundations of Computer Science, IEEE, New York, 1986, pp. 87-96.
[5] Bernard Chazelle and Emo Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete Comput. Geom. 4 (1989), no. 5, 467 – 489. · Zbl 0681.68081 · doi:10.1007/BF02187743
[6] Richard Cole and Chee-K. Yap, Geometric retrieval problems, Inform. and Control 63 (1984), no. 1-2, 39 – 57. · Zbl 0591.68091 · doi:10.1016/S0019-9958(84)80040-6
[7] H. Edelsbrunner and E. Welzl, Halfplanar range search in linear space and \( O({n^{0.695}})\) query time, Inform. Process. Lett. 23 (1986), 289-293. · Zbl 0634.68064
[8] Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Probability and Mathematical Statistics, Vol. 17. · Zbl 0308.05001
[9] Michael L. Fredman, A lower bound on the complexity of orthogonal range queries, J. Assoc. Comput. Mach. 28 (1981), no. 4, 696 – 705. · Zbl 0468.68049 · doi:10.1145/322276.322281
[10] Michael L. Fredman, Lower bounds on the complexity of some optimal data structures, SIAM J. Comput. 10 (1981), no. 1, 1 – 10. · Zbl 0454.68006 · doi:10.1137/0210001
[11] David Haussler and Emo Welzl, \?-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), no. 2, 127 – 151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[12] J. Komlós, E. Szemerédi, and J. Pintz, On Heilbronn’s triangle problem, J. London Math. Soc. (2) 24 (1981), 385-396.
[13] János Komlós, János Pintz, and Endre Szemerédi, A lower bound for Heilbronn’s problem, J. London Math. Soc. (2) 25 (1982), no. 1, 13 – 24. · Zbl 0483.52008 · doi:10.1112/jlms/s2-25.1.13
[14] A. M. Macbeath, A compactness theorem for affine equivalence-classes of convex regions, Canadian J. Math. 3 (1951), 54 – 61. · Zbl 0042.16401
[15] Kurt Mehlhorn, Data structures and algorithms. 3, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin, 1984. Multidimensional searching and computational geometry. · Zbl 0556.68002
[16] W. O. J. Moser, Problems on extremal properties of a finite set of points, Discrete geometry and convexity (New York, 1982) Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 52 – 64. · doi:10.1111/j.1749-6632.1985.tb14538.x
[17] Luis A. Santaló, Integral geometry and geometric probability, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac; Encyclopedia of Mathematics and its Applications, Vol. 1. · Zbl 0342.53049
[18] Dan E. Willard, Polygon retrieval, SIAM J. Comput. 11 (1982), no. 1, 149 – 165. · Zbl 0478.68060 · doi:10.1137/0211012
[19] Andrew C. Yao, On the complexity of maintaining partial sums, SIAM J. Comput. 14 (1985), no. 2, 277 – 288. · Zbl 0564.68072 · doi:10.1137/0214022
[20] F. F. Yao, A \( 3\)-space partition and its applications, Proc. 15th Annual ACM Sympos. on Theory of Comput., ACM, New York, 1983, pp. 258-263.
[21] A. C. Yao and F. F. Yao, On computing the rank function for a set of vectors, Report No. UIUCDCS-R-75-699, Univ. of Illinois at Urbana-Champaign, 1975.
[22] -, A general approach to \( d\)-dimensional geometric queries, Proc. 17th Annual ACM Sympos. on Theory of Comput., ACM, New York, 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.