Abstract
We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, theselazy randomized incremental algorithms are suited for computing structures that have a “nonlocal” definition. In order to analyze these algorithms we generalize some results on random sampling to such situations. We apply our techniques to obtain efficient algorithms for the computation of single cells in arrangements of segments in the plane, single cells in arrangements of triangles in space, and zones in arrangements of hyperplanes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air.Combinatorica, 10(2):137–173, 1990.
J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry.Discrete Comput. Geom., 8:51–71, 1992.
J. D. Boissonnat and K. Dobrindt. Randomized construction of the upper envelope of triangles inR 3.Proc. 4th Canad. Conf. on Computational Geometry, pp. 311–315, 1992.
J.-D. Boissonnat and M. Teillaud. On the randomized construction of the Delaunay tree.Theoret. Comput. Sci., 112:339–354, 1993.
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir and J. Snoeyink. Computing a face in an arrangement of line segments.Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, pp. 441–448, 1991.
L. P. Chew. Building Voronoi Diagrams for Convex Polygons in Linear Expected Time. Technical Report PCS-TR90-147, Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH, 1986.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres.Discrete Comput. Geom., 5:99–160, 1990.
K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions.Comput. Geom. Theory Appl., 3(4):185–212, 1993.
K.L. Clarkson and P.W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom. 4:387–421, 1989.
H. Edelsbrunner, R. Seidel, and M. Sharir. On the zone theorem for hyperplane arrangements.SIAM J. Comput., 22(2):418–429, 1993.
L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams.Algorithmica, 7:381–413, 1992.
L. J. Guibas, M. Sharir, and S. Sifrony. On the general motion planning problem with two degrees of freedom.Discrete Comput. Geom., 4:491–521, 1989.
K. Mehlhorn, S. Meiser, and C. O'Dúnlaing. On the construction of abstract Voronoi diagrams.Discrete Comput. Geom., 6:211–224, 1991.
N. Miller and M. Sharir. Efficient randomized algorithm for constructing the union of fat triangles and of pseudodisks. Manuscript, 1991.
K. Mulmuley. A fast planar partition algorithm, I.Proc. 29th IEEE Symp. on Foundations of Computer Science, pp. 580–589, 1988.
K. Mulmuley.Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, NJ, 1993.
R. Pollack, M. Sharir, and S. Sifrony. Separating two simple polygons by a sequence of translations.Discrete Comput. Geom., 3:123–136, 1987.
O. Schwarzkopf. Dynamic Maintenance of Convex Polytopes and Related Structures. Ph.D. thesis, Fachbereich Mathematik, Freie Universität Berlin, Berlin, June 1992.
R. Seidel. Small-dimensional linear programming and convex hulls made easy.Discrete Comput. Geom., 6:423–434, 1991.
R. Seidel. Backwards analysis of randomized geometric algorithms. In J. Pach, editor,New Trends in Discrete and Computational Geometry, vol. 10 ofAlgorithms and Combinatorics, pp. 37–68. Springer-Verlag, New York, 1993.
B. Tagansky. A new technique for analyzing substructures in arrangements.Proc. 11th Annual ACM Symp. on Computational Geometry, pp. 200–209, 1995.
Author information
Authors and Affiliations
Additional information
This research was supported by the Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). Part of this research was done while K.D. was visiting Utrecht University.
Rights and permissions
About this article
Cite this article
de Berg, M., Dobrindt, K. & Schwarzkopf, O. On lazy randomized incremental construction. Discrete & Computational Geometry 14, 261–286 (1995). https://doi.org/10.1007/BF02570705
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02570705