A sweepline algorithm for Voronoi diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A sweepline algorithm for Voronoi diagrams

Full text

Pdf (717 KB)

Source

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

Yorktown Heights, New York, United States

Pages: 313 - 322

Year of Publication: 1986

ISBN:0-89791-194-6

Author

S Fortune

AT&T Bell Laboratories, Murray Hill, New Jersey

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): 63, Downloads (12 Months): 384, Citation Count: 17

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/10515.10549 What is a DOI?

ABSTRACT

We present a transformation that can be used to compute Voronoi diagrams with a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms have &Ogr;(n log n) worst case running time and use &Ogr;(n) space.

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.

	AE84	F. Aurenhammer, H. Edelsbrunner, An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane, Pattern Recognition 17(2), 1984, pp. 251- 257.
	BWY80	Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
	CD85	L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
	E85	H. Edelsbrunner, private communication, 1985.
	F85	Steven Fortune, A Fast Algorithm for Polygon Containment by Translation (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.189-198, July 15-19, 1985
	GS77	P.J. Green, R. Sibson, Computing Dirichlet Tesselations in the Plane, Computer Journal, 21(22), 1977, pp. 168-173.
	K79	D. Kirkpatrick, Efficient Computation of Continuous Skeletons, Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979, pp. 18-27.
	LD81	D.T. Lee, R.L. Drysdale, Generalizations of Voronoi Diagrams in the Plane, Siam J. Computing 10(1), 1981, pp. 73-87.
	LS80	D.T. Lee, B.J. Schacter, Two Algorithms for Constructing a Delauney Triangulation, International Journal of Computer and Information Sciences, 9(3), 1980, pp. 219- 227+.
	LS85a	D. Lcven,M. Sharir, Intersection Problems and Applications of Voronoi Diagrams, in Advances in Robotics, Vol 1.' Algorithmic and Geometric Aspects of Robotics, J. Schwartz, C.K. Yap, ed. Lawrence Erlbaum Associates, Inc, to appear.
	LS85b	D. Leven, M. Sharir, Planning a Purely Translational Motion for a Convex Object in Two-dimensional Space using Generalized Voronoi Diagrams, Technical Report 34/85, June 1985, Tel Aviv University
	L82	D.T. Lee, Medial Axis Transformation of a Planar Shape, IEEE Trans. Pattern Analysis and Machine Intelligence, VOL PAMI-4, 1982, pp. 363-369.
	OIM84	T. Ohya, M.Iri, K. Murota, Improvements of the Incremental Method for the Voronoi Diagram with Computational Comparison of Various Algorithms, Journal of the Operations Research Society of Japan, Vol 27(4), Dec 1984, pp. 306-336.
	P77	F.P. Preparata, The Medial Axis of a Simple Polygon, Proc. 6th Symp. Math Foundations of Comp. Science, Lecture Notes in Computer Science, Vol 53, Springer-Verla8, New York, pp. 443-450, 1977.
	SH75	M.I. Shamos, D. Hoey, Closest-Point Problems, Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975, pp. 151-162.
	S83	Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
	ST85	N. Sarnak, R.E. Tarjan, Planar Point Location using Persistent Search 'Trees, manuscript, 1985.
	T85	R. Tuminaro, Computation of the Two Dimensional Voronoi Diagram in Expected Linear Time, manuscript, 1985.
	Y84	C.K. Yap, An O(nlogn) Algorithm for the Voronoi Diagram of a Set of Simple Curve Segments, manuscript, October 1984.

CITED BY 17

	R A Dwyer, A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time, Proceedings of the second annual symposium on Computational geometry, p.276-284, June 02-04, 1986, Yorktown Heights, New York, United States
	Helge Backhaus , Stefan Krause, Voronoi-based adaptive scalable transfer revisited: gain and loss of a Voronoi-based peer-to-peer approach for MMOG, Proceedings of the 6th ACM SIGCOMM workshop on Network and system support for games, p.49-54, September 19-20, 2007, Melbourne, Australia
	Ioannis Z. Emiris , Menelaos I. Karavelas, The predicates of the Apollonius diagram: algorithmic analysis and implementation, Computational Geometry: Theory and Applications, v.33 n.1-2, p.18-57, January 2006
	Mehdi Sharifzadeh , Cyrus Shahabi, Utilizing Voronoi Cells of Location Data Streams for Accurate Computation of Aggregate Functions in Sensor Networks, Geoinformatica, v.10 n.1, p.9-36, March 2006
	Yung H. Tsin , Cao-An Wang, Geodesic Voronoi diagrams in the presence of rectilinear barriers, Nordic Journal of Computing, v.3 n.1, p.1-26, Spring 1996
	L. P. Chew, Constrained Delaunay triangulations, Proceedings of the third annual symposium on Computational geometry, p.215-222, June 08-10, 1987, Waterloo, Ontario, Canada
	Gill Barequet , Matthew T. Dickerson , Robert L. Scot Drysdale, 2-Point site Voronoi diagrams, Discrete Applied Mathematics, v.122 n.1-3, p.37-54, 15 October 2002
	Pravin Vaidya, Geometry helps in matching, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.422-425, May 02-04, 1988, Chicago, Illinois, United States
	Stephan Krause, A case for mutual notification: a survey of P2P protocols for massively multiplayer online games, Proceedings of the 7th ACM SIGCOMM Workshop on Network and System Support for Games, October 21-22, 2008, Worcester, Massachusetts
	B. Aronov, On the geodesic Voronoi diagram of point sites in a simple polygon, Proceedings of the third annual symposium on Computational geometry, p.39-49, June 08-10, 1987, Waterloo, Ontario, Canada
	Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999
	C. Wang , L. Schubert, An optimal algorithm for constructing the Delaunay triangulation of a set of line segments, Proceedings of the third annual symposium on Computational geometry, p.223-232, June 08-10, 1987, Waterloo, Ontario, Canada
	Sanguthevar Rajasekaran , Suneeta Ramaswami, Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane and related problems, Proceedings of the tenth annual symposium on Computational geometry, p.57-66, June 06-08, 1994, Stony Brook, New York, United States
	David Lavender , Adrian Bowyer , James Davenport , Andrew Wallis , John Woodwark, Voronoi Diagrams of Set-Theoretic solid Models, IEEE Computer Graphics and Applications, v.12 n.5, p.69-77, September 1992
	Menelaos I. Karavelas , Ioannis Z. Emiris, Root comparison techniques applied to computing the additively weighted Voronoi diagram, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Camil Demetrescu , Irene Finocchi , Giuseppe F. Italiano , Stefan Näher, Visualization in algorithm engineering: tools and techniques, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Richard J. Howarth, Spatial Models for Wide-Area Visual Surveillance: Computational Approaches and Spatial Building-Blocks, Artificial Intelligence Review, v.23 n.2, p.97-155, April 2005