Construction of Voronoi diagrams in the plane by using maps. (English) Zbl 0715.68085

Summary: An algorithm by Guibas and Stolfi (1985) constructs, for a finite set S of n sites in the plane, a triangulation T(S) of S that strictly refines the Delaunay diagram Del(S) when there exists a circle passing through at least four points of S and none of the sites is contained in its interior. For this triangulation T(S) there exist isometries \({\mathcal T}\) such that \({\mathcal T}(T(S))\neq T({\mathcal T}(S))\). The Voronoi diagram Vor(S) is the straight-line dual of Del(S) and the substitution of T(S) into Del(S) leads to needless calculus, indeed to the creation of imaginary vertices for Vor(S). We present here a variant of the Guibas and Stolfi algorithm that determines, with the same complexity, Del(S) and not a triangulation, and uses a simpler data structure. We also give approximation tests of collinearity and cocircularity so that for any similitude \({\mathcal T}\) of the plane, Del(\({\mathcal T}(S))={\mathcal T}(Del(S))\).


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI


[1] Aurenhammer, F., Power diagrams: properties, algorithms and applications, SIAM J. Comput., 16, 1, 78-96 (1987) · Zbl 0616.52007
[2] Chazelle, B.; Edelsbrunner, H., An improved algorithm for constructing \(k\) th order Voronoi diagrams, Proc. 1st ACM Symp. on Computational Geometry, 228-234 (1985)
[3] Cori, R., Un code pour les graphes planaires et ses applications, Asterisque, 27 (1975) · Zbl 0313.05115
[4] Dobkin, D. P.; Laszlo, M. J., Primitives for the manipulation of three-dimensional subdivisions, Algorithmica, 4, 3-32 (1989) · Zbl 0664.68023
[5] Edmonds, J., A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc., 7, 646 (1960)
[6] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer: Springer Berlin · Zbl 0634.52001
[7] Edelsbrunner, H.; Seidel, R., Voronoi diagrams and arrangements, Discrete Comput. Geom., 1, 25-44 (1986) · Zbl 0598.52013
[8] Guibas, L.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, 2, 74-123 (1985) · Zbl 0586.68059
[9] Imai, H.; Iri, M.; Murota, K., Voronoi diagrams in the Laguerre geometry and its applications, SIAM J. Comput., 14, 1, 93-105 (1985) · Zbl 0556.68038
[10] Klein, R.; Wood, D., Voronoi diagrams based on general metrics in the plane, (Cori, R.; Wirsing, M., Proc. STACS 88. Proc. STACS 88, Lecture Notes in Computer Sciences, 294 (1988), Springer: Springer Berlin), 281-291 · Zbl 0649.51006
[11] Preparata, F. P.; Shamos, M. I., Computational Geometry. An Introduction (1985), Springer: Springer Berlin · Zbl 0575.68059
[12] Shamos, M. I.; Hoey, D., Closest-point problems, Proc. 16th Ann. IEEE Symp. on Foundations of Computer Science, 151-162 (1975)
[13] Spehner, J. C., Merging in maps and in pavings, (Publications Laboratoire Mathematiques et Informatique. Publications Laboratoire Mathematiques et Informatique, Theoret. Comput. Sci (1989), Univ. of Haute Alsace: Univ. of Haute Alsace Mulhouse), No. 48 · Zbl 0733.68093
[14] Tutte, W. T., Graph Theory (1984), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0554.05001
[15] Watson, D. F., Computing the \(n\)-dimensional Delaunay triangulation with applications to Voronoi polytopes, Comput. J., 24, 161-172 (1981)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.