Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Drysdale, R.L.S. III: Generalized Voronoi Diagrams and Geometric Searching. PhD thesis, Stanford University, Stanford, CA, USA. AAI7917225 (1979)
Dwyer, R.A.: Higher-dimensional Voronoi diagrams in linear expected time. Discrete. Comput. Geom. 6(3), 343–367 (1991)
Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, vol. 501. Wiley, New York (2009)
Imai, H., Iri, M., Murota, K.: Voronoi diagram in the laguerre geometry and its applications. SIAM J. Comput. 14(1), 93–105 (1985)
Aurenhammer, F.: Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16(1), 78–96 (1987)
Avis, D., Bhattacharya, B.K., Imai, H.: Computing the volume of the union of spheres. Visual Comput. 3(6), 323–328 (1988)
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)
Rycroft, C.: Voro++: A three-dimensional Voronoi cell library in C++ (2009)
CGAL, Computational Geometry Algorithms Library. https://www.cgal.org
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)
Boissonnat, J.D., Wormser, C., Yvinec, M.: Anisotropic diagrams: Labelle Shewchuk approach revisited. Theor. Comput. Sci. 408(2–3), 163–173 (2008)
Emiris, I.Z., Karavelas, M.I.: The predicates of the Apollonius diagram: Algorithmic analysis and implementation. Comput. Geom. 33(1–2), 18–57 (2006)
Boissonnat, J.D., Wormser, C., Yvinec, M.: Curved voronoi diagrams. In: Effective Computational Geometry for Curves and Surfaces, pp 67–116. Springer (2006)
Qiang, D., Faber, V., Gunzburger, M.: Centroidal voronoi tessellations: applications and algorithms. SIAM Rev. 41(4), 637–676 (1999)
Quan, C., Stamm, B.: Mathematical analysis and calculation of molecular surfaces. J. Comput. Phys. 322, 760–782 (2016)
Rockafellar, R.T.: Convex Analysis, Volume 28 of Princeton Mathematics Series. Princeton University Press, Princeton (1970)
McCollum, F.: Power Diagrams (2014)
Olver, F.W.J.: NIST Handbook of Mathematical Functions Hardback and CD-ROM. Cambridge University Press, Cambridge (2010)
Do Carmo, M.P., Do Carmo, M.P.: Differential Geometry of Curves and Surfaces, vol. 2. Prentice-Hall, Englewood Cliffs (1976)
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)
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)
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)
Gerstein, M, Richards, F M: Protein geometry: Volumes areas and distances (2012)
Cazals, F, Dreyfus, T: The structural bioinformatics library: modeling in biomolecular science and beyond. Bioinformatics 33(7), 997–1004 (2016)
Connolly, M.L.: Analytical molecular surface calculation. J. Appl. Crystallogr. 16(5), 548–558 (1983)
Quan, C., Stamm, B.: Meshing molecular surfaces based on analytical implicit representation. J. Molec. Graph. Modell. 71, 200–210 (2017)
Quan, C, Stamm, B: Molecular surface computation package. https://github.com/quanchaoyu/MolSurfComp
Bium, H: A transformation for extracting new descriptions of shape. In: Symposium on Models for the Perception of Speech and Visual Form (1964)
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)
Funding
Open Access funding provided by Projekt DEAL. This work is partially supported by the National Natural Science Foundation of China (Grant No. 11901281).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Tomas Sauer
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
X. Duan and C. Quan are joint first authors who contributed equally to this article.
Appendices
Appendix 1. Proof of Claim 2.2
First, we consider a sphere \(S_{i_{t}} \ni \mathbf {x}\) for a fixed 1 ≤ t ≤ m. According to the definition (24) and Eq. 26, we can compute
where in the third and forth equality, we use the fact that α2(x)|v|2 + x2 = 2α(x)|v|2 and \(\left (\mathbf {n}_{s},\mathbf {v}\right ) =0\) as \(\mathbf {v}_{r}\in \mathcal A_{s}\).
Since (x + λvt, ns) ≤ bs, ∀λ ≥ 0, we know that (vt, ns) ≤ 0. In the case of (vt, ns) < 0, according to Eq. 56, there exists a small enough number \(\varepsilon _{i_{t}}>0\) such that \(\forall x\in [0,\varepsilon _{i_{t}}]\),
Besides, in the case of (vt, ns) = 0 implying \(\mathbf {v}_{t} \in \mathcal {A}_{s}\), according to Eq. 28 and (56), we have ∀0 ≤ x ≤|v|,
In particular, when t = t0, we have both (vt, ns) = 0 and (v,v −vt) = 0. As a consequence,
which means that \(\zeta _{s}(x) \in S_{i_{t_{0}}}\). So far, we have proved that \(\forall x\in [0,\varepsilon _{i_{t}}]\), ζs(x) does not lie in the interior of \(S_{i_{t}}\) and lies on the sphere \(S_{i_{t_{0}}}\).
Second, we consider a sphere \(S_{j}\not \in \{S_{i_{1}}, S_{i_{2}},\ldots ,S_{i_{m}}\}\) that does not contain x. In this case, we have |x −cj|− rj > 0. Therefore, there exists a small number εj > 0 such that ∀x ∈ [0,εj],
This yields that ∀x ∈ [0,εj],
that is to say, ζs(x) lies outside the sphere Sj.
In summary, there exists a possibly small number ε > 0 such that ∀x ∈ [0,ε], ζs(x) does not cross any sphere Si and lies on the sphere \(S_{i_{t_{0}}}\), which implies that ζs(x) ∈Γ.
Appendix 2. Proof of Claim 3.1
Recall the definition of the face
Given a nondegenerate intersection point \(\gamma _{i}^{(0)}\) and the associated 1-patch \(\gamma _{ij}^{(1)}\), the (d − 1)-face Fij is actually a subset of \(\widetilde R_{0}\), since, according to Lemma 3, Fij is a subset of \(\mathcal {R}({\gamma }_{i}^{(0)})\). Further, taking any point \(\mathbf {y}\in \gamma _{ij}^{(1)}\), we have the following result:
As y tends to \(\gamma _{i}^{(0)}\), \(\mathcal {R}(\mathbf {y})\) tends to Fij. Any interior point of \(\mathcal {R}(\mathbf {y})\) has y as a unique closest point, which implies that the interior of \(\mathcal {R}(\mathbf {y})\) lies completely outside \(\widetilde {R}_{0}\). For any point x ∈ Fij, we can then find a sequence of points {xn} outside \(\widetilde {R}_{0}\) converging to x. Therefore, we have \(F_{ij} \subseteq \partial \widetilde {R}_{0}\).
It is sufficient to prove that any point \(\mathbf {x}\in \partial \widetilde {R}_{0}\) belongs to either some face Fij or some set F0 with \(\dim (F_{0})\leq d-2\). \(\partial \widetilde {R}_{0}\) can be divided into two sets
and
In the following content, we prove that if x ∈ U1, then x belongs to a certain face Fij, while if x ∈ U2, then x belongs to F0 which will be defined later.
- Step 1: :
-
In the case of x ∈ U1, we can find a sequence of points {xn} in Ω∖R0 such that xn tends to x. Correspondingly, there exists a sequence of points {an} on Γ, where an is one closest point of xn. Since x has finitely many closest points in \(\widetilde {P}_{0}\) and the total number of k-patches is finite, we can extract a subsequence of an such that this subsequence lies on some k-patch γ(k) with k ≥ 1 and converges to some nondegenerate intersection point \(\gamma _{i}^{(0)}\). Without loss of generality, we can therefore suppose that an tends to \(\gamma _{i}^{(0)}\) and an ∈ γ(k), ∀n. As a consequence, \(\gamma _{i}^{(0)}\) is on the boundary of γ(k) and further, there exists a 1-patch \(\gamma _{ij}^{(1)}\) on \(\overline \gamma ^{(k)}\), satisfying
$$ \mathbf{c}_{\mathcal{I}(\gamma^{(k)})} \subseteq \mathbf{c}_{\mathcal{I}(\gamma_{ij}^{(1)})}. $$(61)Due to the fact that
$$ \mathbf{x}_{n} \in \text{conv}\left( \mathbf{a}_{n},\mathbf{c}_{\mathcal{I}(\gamma^{(k)})}\right), $$(62)we then have
$$ \mathbf{x} \in \text{conv}\left( \gamma_{i}^{(0)},\mathbf{c}_{\mathcal{I}(\gamma^{(k)})}\right) \subseteq \text{conv}\left( \gamma_{i}^{(0)},\mathbf{c}_{\mathcal{I}(\gamma_{ij}^{(1)})}\right) = F_{ij}, $$(63)by taking \(n\rightarrow \infty \).
- Step 2: :
-
In the case of x ∈ U2, we want to prove that x belongs to some F0. According to the definition of U2, x has at least one closest point a that is not a nondegenerate intersection point. Here, we mention the fact that for any point y belonging to the open line segment \(\overline {\mathbf {a}\mathbf {x}}\) with endpoints a and x, a is the unique closest point of y on Γ, which can be easily proven by contradiction.
On the one hand, if a is not an intersection point, then a lies on some k-patch γ(k) with k ≥ 1. According to Theorem 1, we know that
Considering that the latter convex hull, we obtain that \(\mathbf {x}\in \text {conv}(\mathbf {c}_{\mathcal {I}({\gamma ^{(k)}})})\) of dimension \(\dim (\text {conv}(\mathbf {c}_{\mathcal {I}({\gamma ^{(k)}})}))\leq d-2\), since otherwise, x will has a unique closest point on Γ. On the other hand, if a is a degenerate intersection point, then we have \(\mathbf {a} \in {\varLambda }_{\mathcal {I}(\mathbf {a})}\) with \(\dim \left ({\varLambda }_{\mathcal {I}(\mathbf {a})}\right ) \leq d-1\). Since \(\mathcal {R}(\mathbf {a})\subseteq {\varLambda }_{\mathcal {I}(\mathbf {a})}\) according to Theorem 1, it holds that \(\dim \left (\mathcal {R}(\mathbf {a})\right ) \leq d-1\). Here, we actually have \(\mathbf {a}\in \mathcal {R}(\mathbf {a})\) and \(\mathcal {R}(\mathbf {a})\) is a convex set from Lemma 3. Due to the fact mentioned above, we obtain that \(\mathbf {x} \in \mathcal {R}(\mathbf {a})\) only lies on \(\partial \mathcal {R}(\mathbf {a})\) of dimension \(\dim \left (\partial \mathcal {R}(\mathbf {a})\right ) \leq d-2\).
As the number of k-patches and degenerate intersection points are finite, we can conclude that
where \(\gamma _{i}^{(0)}\) in the second union is taken as all degenerate intersection points. Note that the union on the right-hand side of Eq. 65 is of dimension less than or equal to d − 2. This implies that \(\dim (U_{2}) \leq d-2\). Therefore, we can define F0 = U2, which satisfies \(\dim (F_{0}) \leq d-2\).
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Duan, X., Quan, C. & Stamm, B. A boundary-partition-based Voronoi diagram of d-dimensional balls: definition, properties, and applications. Adv Comput Math 46, 44 (2020). https://doi.org/10.1007/s10444-020-09765-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10444-020-09765-3