×

Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks. (English) Zbl 1369.65032


MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Franz Aurenhammer. 1991. Voronoi diagrams – A survey of a fundamental geometric data structure. Computer Surveys 23, 3 (1991), 345–405.
[2] Olivier Devillers. 1998. Improved incremental randomized Delaunay triangulation. In SoCG 98 Proceedings of the 14th ACM Symposium on Computational Geometry. Minneapolis, USA, 106–115.
[3] Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. 2015. Qualitative symbolic perturbation: A new geometry-based perturbation framework. INRIA (2015), 34. · Zbl 1387.68254
[4] R. L. Drysdale and D. T. Lee. 1978. Generalized Voronoi diagram in the plane. 16th Annual Allerton Conference on Communications, Control and Computing (1978), 833–842.
[5] Herbert Edelsbrunner and Ernst Peter Mücke. 1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics 9, 1 (1990), 66–104. · Zbl 0732.68099
[6] Ioannis Z. Emiris and Menelaos I. Karavelas. 2006. The predicates of the Apollonius diagram: Algorithmic analysis and implementation. Computational Geometry - Theory and Applications 33 (2006), 18–57. · Zbl 1082.65021
[7] Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. 2000. On the design of CGAL a computational geometry algorithms library. Software: Practice and Experience 30, 11 (2000), 1167–1202. · Zbl 1147.68781
[8] Steve Fortune. 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica 2 (1987), 153–174. · Zbl 0642.68079
[9] Steven Fortune and Christopher J. Van Wyk. 1993. Efficient exact arithmetic for computational geometry. In Proceedings of the 9th Annual ACM Symposium on Computational Geometry. San Diego, California, 163–172.
[10] Steven Fortune and Christopher J. Van Wyk. 1996. Static analysis yields efficient exact integer arithmetic for computational geometry. ACM Transactions on Graphics 15, 3 (1996), 223–248. · Zbl 05475108
[11] Marina Gavrilova and Jon Rokne. 1999. Swap conditions for dynamic VD for circles and line segments. Computer Aided Geometric Design 16, 2 (1999), 89–106. · Zbl 0909.68186
[12] Marina Gavrilova and Jon Rokne. 2003. Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean d-dimensional space. Computer Aided Geometric Design 20, 4 (2003), 231–242. · Zbl 1069.65554
[13] Jacob E. Goodman and Joseph ORourke. 1997. Handbook of Discrete and Computational Geometry. CRC Press. · Zbl 0890.52001
[14] Gaurav Gupta, R. K. Ghosh, and S. V. Rao. 2003. A routing algorithm for multi-hop mobile ad-hoc networks using weighted Delaunay triangulation. CIT (2003), 1–6.
[15] Martin Held. 1991. On the Computational Geometry of Pocket Machining. Lecture Notes in Computer Science, Vol. 500. Springer-Verlag. · Zbl 0755.68136
[16] Martin Held. 2001. VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments. Computational Geometry - Theory and Applications 18, 2 (2001), 95–123. · Zbl 0976.68162
[17] Martin Held and Stefan Huber. 2009. Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments. Computer-Aided Design 41, 5 (2009), 327–338. · Zbl 1206.65087
[18] Li Jin, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu. 2006. A sweepline algorithm for Euclidean Voronoi diagram of circles. Computer-Aided Design 38, 3 (2006), 260–272. · Zbl 1206.65089
[19] Menelaos Karavelas and Ioannis Z. Emiris. 2002. Predicates for the Planar Additively Weighted Voronoi Diagram. Technical Report ECG-TR-122201-01. INRIA Sophia-Antipolis, Sophia-Antipolis. · Zbl 1092.68692
[20] Menelaos Karavelas and Mariette Yvinec. 2002. Dynamic additively weighted Voronoi diagrams in 2d. In Algorithms-ESA2002. 586–598. · Zbl 1019.68608
[21] Deok-Soo Kim, Youngsong Cho, Joonghyun Ryu, Jae-Kwan Kim, and Donguk Kim. 2013. Anomalies in quasi-triangulations and beta-complexes of spherical atoms in molecules. Computer-Aided Design 45, 1 (2013), 35–52. · Zbl 1055.68598
[22] Deok-Soo Kim, Youngsong Cho, and Kokichi Sugihara. 2010. Quasi-worlds and quasi-operators on quasi-triangulations. Computer-Aided Design 42, 10 (2010), 874–888. · Zbl 1206.65093
[23] Deok-Soo Kim, Youngsong Cho, Kokichi Sugihara, Joonghyun Ryu, and Donguk Kim. 2010. Three-dimensional beta-shapes and beta-complexes via quasi-triangulation. Computer-Aided Design 42, 10 (2010), 911–929. · Zbl 05861754
[24] Deok-Soo Kim, II-Kyu Hwang, and Bum-Joo Park. 1995. Representing the Voronoi diagram of a simple polygon using rational quadratic Bézier curves. Computer-Aided Design 27, 8 (1995), 605–614. · Zbl 0834.65150
[25] Deok-Soo Kim, Donguk Kim, and Kokichi Sugihara. 2001a. Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology. Computer Aided Geometric Design 18 (2001), 541–562. · Zbl 0969.68161
[26] Deok-Soo Kim, Donguk Kim, and Kokichi Sugihara. 2001b. Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry. Computer Aided Geometric Design 18 (2001), 563–585. · Zbl 0969.68162
[27] Deok-Soo Kim, Joonghyun Ryu, Hayong Shin, and Youngsong Cho. 2012. Beta-decomposition for the volume and area of the union of three-dimensional balls and their offsets. Journal of Computational Chemistry 33, 13 (2012), 1252–1273.
[28] Jae-Kwan Kim, Youngsong Cho, Donguk Kim, and Deok-Soo Kim. 2014a. Voronoi diagrams, quasi-triangulations, and beta-complexes for disks in R2: The theory and implementation in BetaConcept. Journal of Computational Design and Engineering 1, 2 (2014), 79–87.
[29] Jae-Kwan Kim, Youngsong Cho, Roman A. Laskowski, Seong Eon Ryu, Kokichi Sugihara, and Deok-Soo Kim. 2014b. BetaVoid: Molecular voids via beta-complexes and Voronoi diagrams. Proteins: Structure, Functions, and Bioinformatics 82, 9 (2014), 1829–1849.
[30] Jae-Kwan Kim, Youngsong Cho, Mokwon Lee, Roman A. Laskowski, Seong Eon Ryu, Kokichi Sugihara, and Deok-Soo Kim. 2015. BetaCavityWeb: A webserver for molecular voids and channels. Nucleic Acids Research 43, W1 (2015), 413–418.
[31] D. T. Lee and R. L. Drysdale. 1981. Generalization of Voronoi diagrams in the plane. SIAM Journal of Computing 10, 1 (1981), 73–87. · Zbl 0454.68083
[32] Kunwoo Lee. 1999. Principles of CAD/CAM/CAE Systems. Addison-Wesley, Boston.
[33] Xiang-Yang Li, Peng-Jun Wan, and Ophir Frieder. 2003. Coverage in wireless ad hoc sensor networks. IEEE Transactions on Computing 52, 6 (2003), 753–763.
[34] Yong-Jin Liu. 2015. Semi-continuity of skeletons in two-manifold and discrete Voronoi approximation. IEEE Transactions on Pattern Analysis and Machine Intelligence 37, 9 (2015), 1938–1944.
[35] Boris D. Lubachevsky. 1991. How to simulate billiards and similar systems. Journal of Computational Physics 94, 2 (1991), 255–283. · Zbl 0716.68094
[36] Boris D. Lubachevsky and Frank H. Stillinger. 1990. Geometric properties of random disk packing. Journal of Statistical Physics 60, 5 (1990), 561–583. · Zbl 1086.82569
[37] Hamid Mahboubi and Amir G. Aghdam. 2013. An energy-efficient strategy to improve coverage in a network of wireless mobile sensors with nonidentical sensing ranges. In Vehicular Technology Conference. 1–5.
[38] Kurt Mehlhorn and Stefan Näher. 1999. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press. · Zbl 0976.68156
[39] T. Nishida and K. Sugihara. 2008. Precision necessary for d-dimensional sphere voronoi diagrams. In Proceedings of the 5th International Symposium on Voronoi Diagrams in Science and Engineering. 22–28. · Zbl 1337.68276
[40] Tetsushi Nishida, Yoshiaki Tanaka, and Kokichi Sugihara. 2007. Evaluation of the Precision for Exact Computation Computation of a Circle Voronoi Diagram. Technical Report 57. Department of Mathematical Informatics Graduate School of Information Science and Technology, University of Tokyo, Bunkyo-ku, Tokyo 113-8656, Japan.
[41] A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu. 1999. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2nd ed.). John Wiley & Sons, Chichester. · Zbl 0946.68144
[42] Packomania. 2014. Packomania Website. (2014). http://www.packomania.com/cciuneq/.
[43] Antonin Pavelka, Eva Sebestova, Barbora Kozlikova, Jan Brezovsky, Jiri Sochor, and Jiri Damborsky. 2016. CAVER: Algorithms for analyzing dynamics of tunnels in macromolecules. Transactions on Computational Biology and Bioinformatics 13, 3 (2016), 505–517.
[44] R. L. Drysdale. 1979. Generalized Voronoi Diagrams and Geometric Searching. Ph.D. Dissertation. Stanford University.
[45] Joonghyun Ryu, Mokwon Lee, Jehyun cha, Roman A. Laskowski, Seong Eon Ryu, and Deok-Soo Kim. 2016. BetaSCPWeb: Side-chain prediction for protein structures using Voronoi diagrams and geometry prioritization. Nucleic Acids Research doi: 10.1093/nar/gkw368 (2016).
[46] Micha Sharir. 1985. Intersection and closest-pair problems for a set of planar discs. SIAM Journal of Computing 14, 2 (1985), 448–468. · Zbl 0564.68052
[47] Eckard Specht. 2016. A precise algorithm to detect voids in polydisperse circle packings. Proceedings of the Royal Society 471, 2182 (2016), 1–19.
[48] Kokichi Sugihara. 1992. A simple method for avoiding numerical errors and degeneracy in Voronoi diagram construction. IEICE Transactions, Fundamentals E75-A (1992), 468–477.
[49] Kokichi Sugihara. 1993. Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams. Graphical Models and Image Processing 55, 6 (1993), 522–531.
[50] Kokichi Sugihara and Masao Iri. 1989. A solid modelling system free from topological inconsistency. Journal of Information Processing 12, 4 (1989), 380–393. · Zbl 0794.68163
[51] Kokichi Sugihara and Masao Iri. 1992. Construction of the Voronoi diagram for “one million” generators in single-precision arithmetic. Proceedings of the IEEE 80, 9 (1992), 1471–1484.
[52] Kokichi Sugihara and Masao Iri. 1994. A robust topology-oriented incremental algorithm for Voronoi diagrams. International Journal of Computational Geometry & Applications 4, 2 (1994), 179–228. · Zbl 0820.68126
[53] Kokichi Sugihara, Masayoshi Sawai, Hiroaki Sano, Deok-Soo Kim, and Donguk Kim. 2004. Disk packing for the estimation of the size of a wire bundle. Japan Journal of Industrial and Applied Mathematics 21, 3 (2004), 259–278. · Zbl 1126.52300
[54] Khuong Vu and Rong Zheng. 2012. Geometric algorithms for target localization and tracking under location uncertainties in wireless sensor networks. In 2012 Proceedings of IEEE INFOCOM. 1835–1843.
[55] Chunxu Xu, Tuanfeng Y. Wang, Yong-Jin Liu, Ligang Liu, and Ying He. 2015. Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes. IEEE Transactions on Visualization and Computer Graphics 21, 7 (2015), 822–834.
[56] Chee-Keng Yap. 1987. An O(nlog n) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete & Computational Geometry 2 (1987), 365–393. · Zbl 0628.68042
[57] Chee-Keng Yap. 1990. A geometric consistency theorem for a symbolic perturbation scheme. Journal of Comput. System Sci. 40 (1990), 2–18. · Zbl 0705.68056
[58] Chee-Keng Yap. 1997. Towards exact geometric computation. Computational Geometry - Theory and Applications 7, 1–2 (1997), 3–23. · Zbl 0869.68104
[59] Jian Yu, Yong Zhou, Isao Tanaka, and Min Yao. 2010. Roll: A new algorithm for the detection of protein pockets and cavities with a rolling probe sphere. Structural Bioinformatics 26, 1 (2010), 46–52. · Zbl 05744407
[60] Zhizhong Zeng, Xinguo Yu, Kun He, Wenqi Huang, and Zhanghua Fu. 2016. Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container. European Journal of Operational Research 250, 2 (2016), 615–627. · Zbl 1346.90526
[61] Al Zimmermann. 2005. Al Zimmermann’s programming Contest. (2005). http://recmath.com/contest/CirclePacking/index.php.
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.