A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams

Full text

Pdf (1.08 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the seventh annual symposium on Computational geometry table of contents

North Conway, New Hampshire, United States

Pages: 142 - 151

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Franz Aurenhammer	Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, Germany
Otfried Schwarzkopf	Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, Germany

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/109648.109664 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.

	AESW	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98567]
	AGSS	A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
	A1	Franz Aurenhammer, A new duality result concerning Voronoi diagrams, Discrete & Computational Geometry, v.5 n.3, p.243-254, May 1990 [doi>10.1007/BF02187788]
	A2	F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
	AS	F. Aurenhammer, O. SchwarzkopL A Simple Online Randomized Incremental Algorithm for Computing Higher Order Voronoi Diagrams. To appear as a Technical Report, Freie Universit~t Berlin, 1991.
	BDSTY	J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, M. Yvinec. Applications of random sampling to online algorithms in computational geometry. Technical report, INRIA, 1990.
	BDT	J.-D. Boissonnat, O. Devillers, M. Teillaud. A randomized incremental algorithm for constructing higher order Voronoi diagrams. Algorithmica, to be published.
	CEGSS	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
	C	K.L. Clarkson. New applications ofrandom sampling in computational geometry. Discrete Comput. Geometry 2 (1987), 195 - 222.
	CS	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 [doi>10.1007/BF02187740]
	DSST	James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
	E	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	GKS	Leonidas J. Guibas , Donald E. Knuth , Micha Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.414-431, July 1990, Warwick University, England
	L	D.T. Lee. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Computers C-31 (1982), 478 - 487.
	MMO	K. Mehlhom, S. Meiser, C. O'Ddnlaing. On the constmction of abstract Voronoi diagrams. Discrete Cornput. Geometry, to be published.
	M	Ketan Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete & Computational Geometry, v.6 n.4, p.307-338, 1991 [doi>10.1007/BF02574692]
	Sc	O. Schwarzkopf. Randomized Incremental Algorithms in a Dynamic Setting. To appear as a Technical Report, Freie Universitiit Berlin, 1991.
	S1	Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
	S2	R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Technical Report B 90--07, Freie UniversiCit Berlin, October 1990.
	W	E. Welzl. Constructing smallest enclosing disks (balls and ellipsoids). To appear as a Technical Report, Freie Universitlit Berlin, 1991.

CITED BY 6

	Xuehou Tan, Optimal computation of the Voronoi diagram of disjoint clusters, Information Processing Letters, v.79 n.3, p.115-119, 07/31/2001
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	Rex A. Dwyer , William F. Eddy, Maximal empty ellipsoids, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.98-102, January 23-25, 1994, Arlington, Virginia, United States
	Sandeep Gupta , Jinfeng Ni , Chinya V. Ravishankar, Efficient data dissemination using locale covers, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Sandeep Gupta , Jinfeng Ni , Chinya V. Ravishankar, Efficient data dissemination using locale covers, Pervasive and Mobile Computing, v.4 n.2, p.254-275, April, 2008
	Ickjai Lee , Kyungmi Lee, AN ORDER-k VORONOI APPROACH TO GEOSPATIAL CONCEPT MANAGEMENT WITHIN CONCEPTUAL SPACES, Applied Artificial Intelligence, v.23 n.6, p.522-537, July 2009