New applications of random sampling in computational geometry. (English) Zbl 0615.68037

For a set \(X\) and integer \(i\), let \(X^i\) be the set of \(i\)-tuples of \(X\). For a positive integer \(n\), let \(\mathfrak n\) denote the set of integers \(\{1,2,\ldots,n\}\). Let \(b(j;t,\alpha)\) be the probability of \(j\) successes out of \(t\) Bernoulli trials with probability of success \(\alpha\). For region \(A\) and for \(B\) a set of regions (subsets) of \(E^d\), let \(\#(A,B)\) be the number of elements of \(B\) that have nonempty intersection with \(A\). The following theorems are proved:
Theorem 1: Let \(S\) and \(\mathfrak F\) be sets of regions of \(E^d\) with \( |S| = s\). For fixed positive integers \(i\) and \(n\), let \(\nu_k\), \(k\in\mathfrak n\), be a collection of mappings from \(S^i\) to \(\mathfrak F\). Let \(R\) be a random sample of \(S\), of size \(r\), and let \(\mathfrak F_R\) be \(\{\nu_k(R^*)\); \(k\in\mathfrak n\), \(R^*\in R^i\}\) the union of the images of \(R^i\) under the \(\nu_k\)’s. Then for integer \(m\) and \(\alpha\in [0,1]\), with \(m\le (r-i)\alpha\),
\[ \operatorname{Prob}\{\exists A\in\mathfrak F_ R \text{ with } \#(A,R)\le m\text{ and }\#(A,S)>\alpha s\}\le O(r^i)\sum_{j\le m}b(j;r-i,\alpha) \]
as \(r\to \infty\). Similarly, for integer \(m\) and \(\alpha\in [0,1]\) with \(m\ge (r-i)\alpha\),
\[ \operatorname{Prob}\{\exists A\in\mathfrak F_ R \text{ with } \#(A,R)\ge m\text{ and } \#(A,S)<\alpha s\}\le O(r^i)\sum_{j\ge m}b(j;r-i,\alpha) \]
as \(r\to \infty\). When \(m\) is much larger than the mean \(\alpha r\), with high probability, every \(\#(A,R)\) is a good estimate of \(\#(A,S)\).
A \(k\)-set of a set of sites (points) \(S\) in \(E^d\) is a subset of \(S\) of size \(k\) that is all on one side of some hyperplane, while the other sites are all on the other side of the hyperplane.
Theorem 2: Let \(g_{k,3}(s)\) be the maximum total number of \((\le k)\)-sets of any set of \(s\) sites in \(E^3\). Then
\[ g_{k,3}(s) = O(sk^2 \log^8s/(\log \log s)^6) \]
\[ \text{(conjecture}\quad g_{k,d}(s) = O(s^{[d/2]}k^{[d/2]})). \]
Theorem 3: One new algorithm is given for searching an arrangement of \(s\) hyperplanes in \(E^d\) in \(O(s^{d+\varepsilon})\) expected time and \(O(s^{d+\varepsilon})\) worst-case space, so that queries may be answered in \(O(\log s)\) time, as \(s\to \infty\), for fixed \(d\) and for any fixed \(\varepsilon >0\).
Theorem 4: The separation of two polytopes \(A,B\subset E^d\) (minimum distance from a point of one to a point of the other) may be computed in expected time \(O((\vert A)^{[d/2]}+(\vert B)^{[d/2]})\) where \(\vert = \) number of vertices and the expectation is with respect to the random behavior of the algorithm. Several lemmas preceding the theorems are interesting by themselves.


68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting
52Bxx Polytopes and polyhedra
52A22 Random convex sets and integral geometry (aspects of convex geometry)


Full Text: DOI EuDML


[1] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension,Proceedings of the 18th Annual SIGACT Symposium, Berkeley, CA, 1986. · Zbl 0697.68079
[2] K. Q. Brown, Voronoi diagrams from convex hull,Inform. Process. Lett.9 (1979), 223-228. · Zbl 0424.68036 · doi:10.1016/0020-0190(79)90074-7
[3] B. Chazelle, How to search in history,Inform. and Control64 (1985), 77-99. · Zbl 0575.68062 · doi:10.1016/S0019-9958(85)80045-0
[4] B. Chazelle and H. Edelsbrunner, An improved algorithm for constructingkth-order Voronoi diagrams,Proceedings of the First Symposium on Computational Geometry, 228-234, Baltimore, MD, 1985.
[5] B. Chazelle and F. P. Preparata, Halfspace range search: an algorithmic application ofk-sets,Discrete Comput. Geom.1 (1986), 83-94. · Zbl 0594.68055 · doi:10.1007/BF02187685
[6] K. L. Clarkson, A probabilistic algorithm for the post office problem,Proceedings of the 17th Annual SIGACT Symposium, 75-184, Providence, RI, 1985.
[7] R. Cole, Partitioning Point Sets in Arbitrary Dimensions, Technical Report 184, Department of Computer Science, Courant Institute, New York, 1985.
[8] R. Cole and C. K. Yap, Geometric retrieval problems,Inform. and Control63 (1984), 112-121. · Zbl 0591.68091 · doi:10.1016/S0019-9958(84)80040-6
[9] R. Cole, M. Sharir, and C. Yap, Onk-hulls and related problems,Proceedings of the 16th Annual SIGACT Symposium, 154-166, Washington, DC, 1984. · Zbl 0637.68074
[10] D. P. Dobkin and D. G. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra,J. Algorithms6 (1985), 381-393. · Zbl 0577.52004 · doi:10.1016/0196-6774(85)90007-0
[11] D. Dobkin and R. J. Lipton, Multidimensional searching problems,SIAM J. Comput.5 (1976), 181-186. · Zbl 0333.68031 · doi:10.1137/0205015
[12] H. Edelsbrunner and R. Seidel, Voronoi diagrams and arrangements,Discrete Comput. Geom.1 (1986), 25-44. · Zbl 0598.52013 · doi:10.1007/BF02187681
[13] H. Edelsbrunner and E. Welzl, On the number of line separations of a finite set in the plane,J. Combin. Theory Ser. A38 (1985), 15-29. · Zbl 0616.52003 · doi:10.1016/0097-3165(85)90017-2
[14] H. Edelsbrunner, J. O’Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput.15 (1986), 341-363. · Zbl 0603.68104 · doi:10.1137/0215024
[15] P. Erdös and J. Spencer,Probabilistic Methods in Combinatorics, Academic Press, New York, 1974. · Zbl 0308.05001
[16] Erdös, P.; Lovasz, L.; Simmons, A.; Straus, E. G.; Srivastava, J. N. (ed.); etal., Dissection graphs of planar point sets (1973), Amsterdam
[17] B. Grünbaum,Convex Polytopes, Wiley, New York, 1967. · Zbl 0163.16603
[18] D. Haussler and E. Welzl,ε-nets and simplex range queries,Discrete Comput. Geom.2 (1987), 127-151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[19] C. A. R. Hoare, Quicksort,Comput. J.5 (1962), 13-28. · Zbl 0108.13601
[20] D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[21] D. T. Lee, Onk-nearest neighbor Voronoi diagrams in the plane,IEEE Trans. Comput.,31 (1982), 478-487. · Zbl 0491.68062
[22] P. McMullen, The maximum number of faces of a convex polytope,Mathematika17 (1970), 179-184. · Zbl 0217.46703 · doi:10.1112/S0025579300002850
[23] F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[24] R. Reischuk, A fast probabilistic parallel sorting algorithm,Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 212-219, 1981.
[25] R. Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face,Proceedings of the 18th Annual SIGACT Symposium, Berkeley, CA, 1986.
[26] M. I. Shamos, Computational Geometry, Ph.D. thesis, Yale University, 1978.
[27] V. N. Vapnik and A. Y. A. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl.16 (1971). · Zbl 0247.60005
[28] J. S. Vitter, Optimum algorithms for two random sampling problems,Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, 65-75, Tucson, AZ, 1983.
[29] D. Willard, Polygon retrieval,SIAM J. Comput.11 (1982). · Zbl 0478.68060
[30] A. C. Yao and F. F. Yao, A general approach tod-dimensional geometric queries,Proceedings of the 17th Annual SIGACT Symposium, 163-168, Providence, RI, 1985.
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.