zbMATH — the first resource for mathematics

A boundary-partition-based Voronoi diagram of \(d\)-dimensional balls: definition, properties, and applications. (English) Zbl 1451.52009
Summary: In computational geometry, different ways of space partitioning have been developed, including the Voronoi diagram of points and the power diagram of balls. In this article, a generalized Voronoi partition of overlapping \(d\)-dimensional balls, called the boundary-partition-based diagram, is proposed. The definition, properties, and applications of this diagram are presented. Compared to the power diagram, this boundary-partition-based diagram is straightforward in the computation of the volume of overlapping balls, which avoids the possibly complicated construction of power cells. Furthermore, it can be applied to characterize singularities on molecular surfaces and to compute the medial axis that can potentially be used to classify molecular structures.
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
Full Text: DOI
[1] Drysdale, R.L.S. III: Generalized Voronoi Diagrams and Geometric Searching. PhD thesis, Stanford University, Stanford, CA, USA. AAI7917225 (1979)
[2] Dwyer, RA, Higher-dimensional Voronoi diagrams in linear expected time, Discrete. Comput. Geom., 6, 3, 343-367 (1991) · Zbl 0727.68128
[3] Okabe, A.; Boots, B.; Sugihara, K.; Chiu, SN, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, vol. 501 (2009), New York: Wiley, New York
[4] Imai, H.; Iri, M.; Murota, K., Voronoi diagram in the laguerre geometry and its applications, SIAM J. Comput., 14, 1, 93-105 (1985) · Zbl 0556.68038
[5] Aurenhammer, F., Power diagrams: Properties, algorithms and applications, SIAM J. Comput., 16, 1, 78-96 (1987) · Zbl 0616.52007
[6] Avis, D.; Bhattacharya, BK; Imai, H., Computing the volume of the union of spheres, Visual Comput., 3, 6, 323-328 (1988) · Zbl 0646.68051
[7] Cazals, F.; Kanhere, H.; Loriot, S., Computing the volume of a union of balls: a certified algorithm, ACM Trans. Math. Softw., 38, 1, 3 (2011) · Zbl 1365.65039
[8] Rycroft, C.: Voro++: A three-dimensional Voronoi cell library in C++ (2009)
[9] CGAL, Computational Geometry Algorithms Library. https://www.cgal.org · Zbl 1322.68279
[10] Boissonnat, J.D., Karavelas, M.I.: On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 305-312. Society for Industrial and Applied Mathematics (2003) · Zbl 1094.68676
[11] Boissonnat, JD; Wormser, C.; Yvinec, M., Anisotropic diagrams: Labelle Shewchuk approach revisited, Theor. Comput. Sci., 408, 2-3, 163-173 (2008) · Zbl 1157.68068
[12] Emiris, IZ; Karavelas, MI, The predicates of the Apollonius diagram: Algorithmic analysis and implementation, Comput. Geom., 33, 1-2, 18-57 (2006) · Zbl 1082.65021
[13] Boissonnat, J.D., Wormser, C., Yvinec, M.: Curved voronoi diagrams. In: Effective Computational Geometry for Curves and Surfaces, pp 67-116. Springer (2006) · Zbl 1116.65021
[14] Qiang, D.; Faber, V.; Gunzburger, M., Centroidal voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676 (1999) · Zbl 0983.65021
[15] Quan, C.; Stamm, B., Mathematical analysis and calculation of molecular surfaces, J. Comput. Phys., 322, 760-782 (2016) · Zbl 1351.82052
[16] Rockafellar, RT, Convex Analysis, Volume 28 of Princeton Mathematics Series (1970), Princeton: Princeton University Press, Princeton
[17] McCollum, F.: Power Diagrams (2014)
[18] Olver, FWJ, NIST Handbook of Mathematical Functions Hardback and CD-ROM (2010), Cambridge: Cambridge University Press, Cambridge
[19] Do Carmo, M.P., Do Carmo, M.P.: Differential Geometry of Curves and Surfaces, vol. 2. Prentice-Hall, Englewood Cliffs (1976) · Zbl 0326.53001
[20] Brendan, J.; McConkey, VS; Edelman, M., Quantification of protein surfaces, volumes and atom-atom contacts using a constrained Voronoi procedure, Bioinformatics, 18, 10, 1365-1373 (2002)
[21] Rother, K.; Hildebrand, PW; Goede, A.; Gruening, B.; Preissner, R., Voronoia: Analyzing packing in protein structures, Nucleic Acids Res., 37, suppl_1, D393-D395 (2008)
[22] Till, MS; Ullmann, GM, McVol-A program for calculating protein volumes and identifying cavities by a Monte Carlo algorithm, J. Mol. Model., 16, 3, 419-429 (2010)
[23] Gerstein, M, Richards, F M: Protein geometry: Volumes areas and distances (2012)
[24] Cazals, F.; Dreyfus, T., The structural bioinformatics library: modeling in biomolecular science and beyond, Bioinformatics, 33, 7, 997-1004 (2016)
[25] Connolly, ML, Analytical molecular surface calculation, J. Appl. Crystallogr., 16, 5, 548-558 (1983)
[26] Quan, C.; Stamm, B., Meshing molecular surfaces based on analytical implicit representation, J. Molec. Graph. Modell., 71, 200-210 (2017)
[27] Quan, C, Stamm, B: Molecular surface computation package. https://github.com/quanchaoyu/MolSurfComp · Zbl 1351.82052
[28] Bium, H: A transformation for extracting new descriptions of shape. In: Symposium on Models for the Perception of Speech and Visual Form (1964)
[29] Lieutier, A., Any open bounded subset of rn has the same homotopy type as its medial axis, Comput. Aided Des., 36, 11, 1029-1046 (2004)
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.