On lazy randomized incremental construction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On lazy randomized incremental construction

Full text

Pdf (1.09 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 105 - 114

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Mark de Berg	Vakgroep Informatica, Universiteit Utrecht, Postbus 80.089, 3508, TB Utrecht, the Netherlands
Katrin Dobrindt	INRIA, B.P. 93, 06902 Sophia-Antipolis Cedex, France
Otfried Schwarzkopf	Vakgroep Informatica, Universiteit Utrecht, Postbus 80.089, 3508, TB Utrecht, the Netherlands

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195113 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AS90	B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air. Combinatorica, 10(2):137-173, 1990.
	AS92	Boris Aronov , Micha Sharir, Castles in the air revisited, Proceedings of the eighth annual symposium on Computational geometry, p.146-156, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142710]
	BD92	J.D. Boissonnat and K. Dobrindt. Randomized construction of the upper envelope of triangles in R3. In Proc. 4th Canad. Conf. Comput. Geom., pages 311-315, 1992.
	BDS+92	Jean-Daniel Boissonnat , Olivier Devillers , René Schott , Monique Teillaud , Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, v.8 n.1, p.51-71, 1992 [doi>10.1007/BF02293035]
	BT93	Jean-Daniel Boissonnat , Monique Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, v.112 n.2, p.339-354, May 10, 1993 [doi>10.1016/0304-3975(93)90024-N ]
	CEG+90	Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990
	CEG+91	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.441-448, January 28-30, 1991, San Francisco, California, United States
	Che85	L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
	CMS93	Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U ]
	CS89	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989
	dBGH94	Marc de Berg , Leonidas J. Guibas , Dan Halperin, Vertical decompositions for triangles in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.1-10, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177427]
	ESS93	Herbert Edelsbrunner , Raimund Seidel , Micha Sharir, On the zone theorem for hyperplane arrangements, SIAM Journal on Computing, v.22 n.2, p.418-429, April 1993 [doi>10.1137/0222031]
	GKS92	L.J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunav and Voronoi diagrams. Algorithmica, 7:381-413. 1992.
	GSS89	L. J. Guibas, On the general motion-planning problem with two degrees of freedom, Discrete & Computational Geometry, v.4 n.5, p.491-521, 1989
	MMÓ91	K. Mehlhorn , St. Meiser , C. O'Dúnlaing, On the construction of abstract Voronoi diagrams, Discrete & Computational Geometry, v.6 n.3, p.211-224, 1991
	MS91	N. Miller and M. Sharir. Efficient randomized algorithm for constructing the union of fat triangles and of pseudodiscs. Manuscript, 1991.
	Mul88	K. Mulmuley. A fast planar partition algorithm, i. In Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci., pages 580-589, 1988.
	Mul93	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, New York, 1993.
	PSS87	R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988
	Sch92	O. Schwarzkopf. Dynamic Maintenance of Convex Polytopes and Related Structures. Ph.D. thesis, Fachbereich Mathematik, Freie Universit~t Berlin, Berlin, Germany, June 1992.
	Sei91	Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991
	Sei93	R. Seidel. Backwards analysis of randomized geometric algorithms. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume 10 of Algorithms and Combinatorics. pages 37-68. Springer-Verlag, 1993.
	Sha91	M. Sharir. On k-sets in arrangements of curves and surfaces. Discrete Comput. Geom., 6:593- 613, 1991.

CITED BY 7

	Pankaj K. Agarwal , Jiří Matoušek , Otfried Schwarzkopf, Computing many faces in arrangements of lines and segments, Proceedings of the tenth annual symposium on Computational geometry, p.76-84, June 06-08, 1994, Stony Brook, New York, United States
	Pankaj K. Agarwal , Otfried Schwarzkopf , Micha Sharir, The overlay of lower envelopes in three dimensions and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.182-189, June 05-07, 1995, Vancouver, British Columbia, Canada
	Pankaj K. Agarwal , Mark de Berg , Jiří Matoušek , Otfried Schwarzkopf, Constructing levels in arrangements and higher order Voronoi diagrams, Proceedings of the tenth annual symposium on Computational geometry, p.67-75, June 06-08, 1994, Stony Brook, New York, United States
	Boaz Tagansky, A new technique for analyzing substructures in arrangements, Proceedings of the eleventh annual symposium on Computational geometry, p.200-210, June 05-07, 1995, Vancouver, British Columbia, Canada
	Pankaj K. Agarwal , Micha Sharir, Efficient randomized algorithms for some geometric optimization problems, Proceedings of the eleventh annual symposium on Computational geometry, p.326-335, June 05-07, 1995, Vancouver, British Columbia, Canada
	Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Computing envelopes in four dimensions with applications, Proceedings of the tenth annual symposium on Computational geometry, p.348-358, June 06-08, 1994, Stony Brook, New York, United States
	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing faces in segment and simplex arrangements, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.672-682, May 29-June 01, 1995, Las Vegas, Nevada, United States