×

A dynamic sampling approach towards computing Voronoi diagram of a set of circles. (English) Zbl 1505.65133

Summary: Discretizing the input curves into points or lines is a way of constructing an approximate Voronoi diagram. Sampling the input curves into points requires a fine sample density to obtain a reasonable topological and geometrical accuracy of the Voronoi diagram. In this work, it is shown that an accurate computation of the Voronoi diagram for a set of circles employing a very coarse sample set is possible. The approach proposes the selection of varying number of sample points on each circle dynamically, using the Delaunay graph of center points of circles. We then show that this approach can be used to identify neighborhood information of the circles. The touching disc method is then used to construct the Voronoi diagram with an algorithmic complexity of \(O(n \log n)\). The work also demonstrates the robustness and theoretical correctness of the proposed algorithm by considering inputs in non-general position and for a large number of circles of the order of \(10^5\).

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Software:

VOROPACK-D; QTFier; CGAL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aichholzer, O.; Aigner, W.; Aurenhammer, F.; Hackl, T.; Jüttler, B.; Rabl, M., Medial axis computation for planar free-form shapes, Comput. Aided Des., 41, 339-349 (2009)
[2] Cornea, N. D.; Silver, D.; Min, P., Curve-skeleton properties, applications, and algorithms, IEEE Trans. Vis. Comput. Graph., 13, 530 (2007)
[3] Devillers, O., Improved incremental randomized Delaunay triangulation, (Proceedings of the Fourteenth Annual Symposium on Computational Geometry (1998)), 106-115
[4] Devillers, O.; Karavelas, M.; Teillaud, M., Qualitative symbolic perturbation: a new geometry-based perturbation framework, INRIA, 34 (2015)
[5] Edelsbrunner, H.; Mücke, E. P., Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Trans. Graph., 9, 66-104 (1990) · Zbl 0732.68099
[6] Emiris, I. Z.; Karavelas, M. I., The predicates of the Apollonius diagram: algorithmic analysis and implementation, Comput. Geom., 33, 18-57 (2006) · Zbl 1082.65021
[7] Gavrilova, M. L.; Rokne, J., Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean d-dimensional space, Comput. Aided Geom. Des., 20, 231-242 (2003) · Zbl 1069.65554
[8] Hu, Z.; Li, X.; Krishnamurthy, A.; Hanniel, I.; McMains, S., Voronoi cells of non-general position spheres using the GPU, Comput-Aided Des. Appl., 14, 572-581 (2017)
[9] Jin, L.; Kim, D.; Mu, L.; Kim, D. S.; Hu, S. M., A sweepline algorithm for Euclidean Voronoi diagram of circles, Comput. Aided Des., 38, 260-272 (2006) · Zbl 1206.65089
[10] Karavelas, M. I.; Yvinec, M., Dynamic additively weighted Voronoi diagrams in 2D, (European Symposium on Algorithms (2002), Springer), 586-598 · Zbl 1019.68608
[11] Kim, D. S.; Cho, Y.; Sugihara, K., Quasi-worlds and quasi-operators on quasi-triangulations, Comput. Aided Des., 42, 874-888 (2010) · Zbl 1206.65093
[12] Kim, D. S.; Kim, D.; Sugihara, K., Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology, Comput. Aided Geom. Des., 18, 541-562 (2001) · Zbl 0969.68161
[13] Kim, D. S.; Kim, D.; Sugihara, K., Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry, Comput. Aided Geom. Des., 18, 563-585 (2001) · Zbl 0969.68162
[14] Lee, D. T.; Drysdale, R. L., Generalization of Voronoi diagrams in the plane, SIAM J. Comput., 10, 73-87 (1981) · Zbl 0454.68083
[15] Lee, M.; Sugihara, K.; Kim, D. S., Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks, ACM Trans. Math. Softw., 43, 1-23 (2016) · Zbl 1369.65032
[16] Li, X.; Krishnamurthy, A.; Hanniel, I.; McMains, S., Edge topology construction of Voronoi diagrams of spheres in non-general position, Comput. Graph., 82, 332-342 (2019)
[17] Mahboubi, H.; Aghdam, A. G., An energy-efficient strategy to improve coverage in a network of wireless mobile sensors with nonidentical sensing ranges, (2013 IEEE 77th Vehicular Technology Conference (VTC Spring) (2013)), 1-5
[18] Rappaport, D., A convex hull algorithm for discs, and applications, Comput. Geom., 1, 171-187 (1992) · Zbl 0772.68108
[19] Ryu, J.; Lee, M.; Kim, D.; Kallrath, J.; Sugihara, K.; Kim, D. S., Voropack-d: real-time disk packing algorithm using Voronoi diagram, Appl. Math. Comput., 375, Article 125076 pp. (2020)
[20] Sharir, M., Intersection and closest-pair problems for a set of planar discs, SIAM J. Comput., 14, 448-468 (1985) · Zbl 0564.68052
[21] Sugihara, K., A simple method for avoiding numerical errors and degeneracy in Voronoi diagram construction, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 75, 468-477 (1992)
[22] Sugihara, K., Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams, CVGIP, Graph. Models Image Process., 55, 522-531 (1993)
[23] Sugihara, K.; Iri, M., Construction of the Voronoi diagram for “one million” generators in single-precision arithmetic, Proc. IEEE, 80, 1471-1484 (1992)
[24] Sugihara, K.; Sawai, M.; Sano, H.; Kim, D. S.; Kim, D., Disk packing for the estimation of the size of a wire bundle, Jpn. J. Ind. Appl. Math., 21, 259-278 (2004) · Zbl 1126.52300
[25] Sundar, B. R.; Mukundan, M. K.; Muthuganapathy, R., A unified approach towards computing Voronoi diagram, medial axis, Delaunay graph and α-hull of planar closed curves using touching discs, Comput. Graph., 89, 131-143 (2020)
[26] The CGAL Project, 2020. CGAL User and Reference Manual. 5.2 ed., CGAL Editorial Board.
[27] Wang, P.; Yuan, N.; Ma, Y.; Xin, S.; He, Y.; Chen, S.; Xu, J.; Wang, W., Robust computation of 3D Apollonius diagrams, (Computer Graphics Forum (2020), Wiley Online Library), 43-55
[28] Yap, C. K., Symbolic treatment of geometric degeneracies, J. Symb. Comput., 10, 349-370 (1990) · Zbl 0717.68107
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.