Abstract
This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry. One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer. This algorithm requiresO(s d+ε) expected preprocessing time to build a search structure for an arrangement ofs hyperplanes ind dimensions. The expectation, as with all expected times reported here, is with respect to the random behavior of the algorithm, and holds for any input. Given the data structure, and a query pointp, the cell of the arrangement containingp can be found inO(logs) worst-case time. (The bound holds for any fixed ε>0, with the constant factors dependent ond and ε.) Using point-plane duality, the algorithm may be used for answering halfspace range queries. Another algorithm finds random samples of simplices to determine the separation distance of two polytopes. The algorithm uses expectedO(n [d/2]) time, wheren is the total number of vertices of the two polytopes. This matches previous results [10] for the cased = 3 and extends them. Another algorithm samples points in the plane to determine their orderk Voronoi diagram, and requires expectedO(s 1+ε k) time fors points. (It is assumed that no four of the points are cocircular.) This sharpens the boundO(sk 2 logs) for Lee's algorithm [21], andO(s 2 logs+k(s−k) log2 s) for Chazelle and Edelsbrunner's algorithm [4]. Finally, random sampling is used to show that any set ofs points inE 3 hasO(sk 2 log8 s/(log logs)6) distinctj-sets withj≤k. (ForS ⊂E d, a setS′ ⊂S with |S′| =j is aj-set ofS if there is a half-spaceh + withS′ =S ∩h +.) This sharpens with respect tok the previous boundO(sk 5) [5]. The proof of the bound given here is an instance of a “probabilistic method” [15].
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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.
K. Q. Brown, Voronoi diagrams from convex hull,Inform. Process. Lett. 9 (1979), 223–228.
B. Chazelle, How to search in history,Inform. and Control 64 (1985), 77–99.
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.
B. Chazelle and F. P. Preparata, Halfspace range search: an algorithmic application ofk-sets,Discrete Comput. Geom. 1 (1986), 83–94.
K. L. Clarkson, A probabilistic algorithm for the post office problem,Proceedings of the 17th Annual SIGACT Symposium, 75–184, Providence, RI, 1985.
R. Cole, Partitioning Point Sets in Arbitrary Dimensions, Technical Report 184, Department of Computer Science, Courant Institute, New York, 1985.
R. Cole and C. K. Yap, Geometric retrieval problems,Inform. and Control 63 (1984), 112–121.
R. Cole, M. Sharir, and C. Yap, Onk-hulls and related problems,Proceedings of the 16th Annual SIGACT Symposium, 154–166, Washington, DC, 1984.
D. P. Dobkin and D. G. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra,J. Algorithms 6 (1985), 381–393.
D. Dobkin and R. J. Lipton, Multidimensional searching problems,SIAM J. Comput. 5 (1976), 181–186.
H. Edelsbrunner and R. Seidel, Voronoi diagrams and arrangements,Discrete Comput. Geom. 1 (1986), 25–44.
H. Edelsbrunner and E. Welzl, On the number of line separations of a finite set in the plane,J. Combin. Theory Ser. A 38 (1985), 15–29.
H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341–363.
P. Erdös and J. Spencer,Probabilistic Methods in Combinatorics, Academic Press, New York, 1974.
P. Erdös, L. Lovasz, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, inA Survey of Combinatorial Theory (J. N. Srivastavaet al., eds), North-Holland, Amsterdam 1973.
B. Grünbaum,Convex Polytopes, Wiley, New York, 1967.
D. Haussler and E. Welzl,ε-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127–151.
C. A. R. Hoare, Quicksort,Comput. J. 5 (1962), 13–28.
D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.
D. T. Lee, Onk-nearest neighbor Voronoi diagrams in the plane,IEEE Trans. Comput.,31 (1982), 478–487.
P. McMullen, The maximum number of faces of a convex polytope,Mathematika 17 (1970), 179–184.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
R. Reischuk, A fast probabilistic parallel sorting algorithm,Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 212–219, 1981.
R. Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face,Proceedings of the 18th Annual SIGACT Symposium, Berkeley, CA, 1986.
M. I. Shamos, Computational Geometry, Ph.D. thesis, Yale University, 1978.
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).
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.
D. Willard, Polygon retrieval,SIAM J. Comput. 11 (1982).
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.
Author information
Authors and Affiliations
Additional information
A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA, 1986.
Rights and permissions
About this article
Cite this article
Clarkson, K.L. New applications of random sampling in computational geometry. Discrete Comput Geom 2, 195–222 (1987). https://doi.org/10.1007/BF02187879
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187879