×

zbMATH — the first resource for mathematics

A linear-time algorithm for computing the Voronoi diagram of a convex polygon. (English) Zbl 0696.68045
The main result of the paper is a linear-time algorithm for the problem of constructing the convex hull of a set of n points in three dimensions whose projections on the xy plane form the (counterclockwise ordered) set of vertices of a convex polygon.
As consequences, linear time algorithms are obtained for computing the Voronoi diagram and the furthest-point Voronoi diagram for a convex polyon vertex set, for updating the Voronoi diagram after deletion of a point site, for constructing the medial axis of a convex polygon, for finding the largest inscribed circle and the largest empty circle centered inside a convex polygon. These results are also used to obtain better time bounds for some algorithms for proximity-related problems. Some open problems are posed.
Reviewer: N.Korneenko

MSC:
68Q25 Analysis of algorithms and problem complexity
68U99 Computing methodologies and applications
52A10 Convex sets in \(2\) dimensions (including convex curves)
52A15 Convex sets in \(3\) dimensions (including convex surfaces)
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] L. P. Chew, Constrained Delaunay triangulations,Proc. 3rd Annual ACM Symposium on Computational Geometry, 1987, pp. 223-232.
[2] Guibas, L. J.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, 74-123, (1985) · Zbl 0586.68059
[3] D. G. Kirkpatrick, Efficient computation of continuous skeletons,Proc. 20th IEEE Annual Symposium on Foundations of Computer Science, 1979, pp. 18-27.
[4] Kirkpatrick, D. G., Optimal search in planar subdivisions, SIAM J. Comput., 12, 28-35, (1983) · Zbl 0501.68034
[5] Lee, D. T., On \(k\)-nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Comput., 31, 478-487, (1982) · Zbl 0491.68062
[6] Lee, D. T.; Lin, A. K., Generalized Delaunay triangulations of planar graphs, Discrete Comput. Geom., 1, 201-217, (1986) · Zbl 0596.52007
[7] McCallum, D.; Avis, D., A linear-time algorithm for finding the convex hull of a simple polygon, Inform. Process. Lett., 9, 201-206, (1979) · Zbl 0423.68031
[8] Preparata, F. P., The medial axis of a simple polygon, 443-450, (1977), Berlin · Zbl 0361.50003
[9] F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. · Zbl 0759.68037
[10] M. I. Shamos, Computational Geometry, Ph.D. thesis, Yale University, New Haven, CT, 1978.
[11] C. A. Wang and L. Schubert, An optimal algorithm for constructing the Delaunay triangulation of a set of segments,Proc. 3rd Annual ACM Symposium on Computational Geometry, 1987, pp. 223-232.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.