A Linear time algorithm for computing the Voronoi diagram of a convex polygon

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Linear time algorithm for computing the Voronoi diagram of a convex polygon

Full text

Pdf (791 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents

New York, New York, United States

Pages: 39 - 45

Year of Publication: 1987

ISBN:0-89791-221-7

Authors

A. Aggarwal	IBM T. J. Watson Center Yorktown Heights, NY
L. Guibas	Stanford University, Stanford, CA and DEC Systems Research Center, Palo Alto, CA
J. Saxe	DEC Systems Research Center, Palo Alto, CA
P. Shor	AT&T Bell Labs, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 76, Citation Count: 6

Additional Information:

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

ABSTRACT

We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram of n points in the plane can be computed in &THgr;(n) time when these points form the vertices of a convex polygon in, say, counterclockwise order. This settles an outstanding open problem in computational geometry. Our techniques can also be used to obtain linear time algorithms for computing the farthest-point Voronoi diagram and the medial axis of a convex polygon and for deleting a vertex from a general planar Voronoi diagram.

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.

	ART86	A. Aggarwal, P. Raghavan and P. Tiwa,ri, "Lower Bounds for Computing the Closest-Pair in Simple Polygons and Related Problems," manuscript, in preparation.
	CA79	D. McCallum and D. Avis, "A Linear Time Algorithm for Finding the Convex Hull of a Simple Polygon," Info. Proc. Letters, Vol. 9, pp. 210-206, 1979.
	GS85	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	Ki79	D.G. Kirkp~trick, "Efficient Computation of Continuous Skeletons," Proc. of the 20th Annum IEEE Symposium on the Founda{tions of Computer Science, pp. 18-27, 1979.
	Ki83	D.G. Kirkpatrick, "Optimal Search in Planar Subdivisions." SIAM J. of C, omputing, Vol. 12, No. 1, pp. 28-35, 1983.
	LL86	D.T. Lee and A. K. Lin, "Generalized Delaunay Triangulations of Planar Graphs," Discrete and Computational Geometry, to appear.
	Pr77	F.P. Preparata, "The Medici Axis of a Simple Polygon," Proc. of the 6th Symposium on M~thematical Foundations of Computer Science, pp. 443-450. Sept. 1977.
	PS85	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	Sh78	Michael Ian Shamos, Computational geometry., 1978
	Su83	Kenneth J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, Journal of the ACM (JACM), v.30 n.3, p.428-448, July 1983 [doi>10.1145/2402.322386]

CITED BY 6

	K. Mulmuley, Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.322-330, May 13-17, 1990, Baltimore, Maryland, United States
	A. Aggarwal , H. Imai , N. Katoh , S. Suri, Fining k points with minimum spanning trees and related problems, Proceedings of the fifth annual symposium on Computational geometry, p.283-291, June 05-07, 1989, Saarbruchen, West Germany
	Ketan Mulmuley, Randomized multidimensional search trees (extended abstract): dynamic sampling, Proceedings of the seventh annual symposium on Computational geometry, p.121-131, June 10-12, 1991, North Conway, New Hampshire, United States
	Dina Kravets , James K. Park, Selection and sorting in totally monotone arrays, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.494-502, January 22-24, 1990, San Francisco, California, United States
	A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States
	Sasanka Roy , Debabrata Bardhan , Sandip Das, Base station placement on boundary of a convex polygon, Journal of Parallel and Distributed Computing, v.68 n.2, p.265-273, February, 2008