{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T13:52:59Z","timestamp":1762005179098,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T00:00:00Z","timestamp":1588723200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T00:00:00Z","timestamp":1588723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Adv Comput Math"],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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<jats:italic>d<\/jats:italic>-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.<\/jats:p>","DOI":"10.1007\/s10444-020-09765-3","type":"journal-article","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T13:03:56Z","timestamp":1588770236000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A boundary-partition-based Voronoi diagram of d-dimensional balls: definition, properties, and applications"],"prefix":"10.1007","volume":"46","author":[{"given":"Xianglong","family":"Duan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chaoyu","family":"Quan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3375-483X","authenticated-orcid":false,"given":"Benjamin","family":"Stamm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,6]]},"reference":[{"key":"9765_CR1","unstructured":"Drysdale, R.L.S. III: Generalized Voronoi Diagrams and Geometric Searching. PhD thesis, Stanford University, Stanford, CA, USA. AAI7917225 (1979)"},{"issue":"3","key":"9765_CR2","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02574694","volume":"6","author":"RA Dwyer","year":"1991","unstructured":"Dwyer, R.A.: Higher-dimensional Voronoi diagrams in linear expected time. Discrete. Comput. Geom. 6(3), 343\u2013367 (1991)","journal-title":"Discrete. Comput. Geom."},{"key":"9765_CR3","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, vol. 501","author":"A Okabe","year":"2009","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, vol. 501. Wiley, New York (2009)"},{"issue":"1","key":"9765_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/0214006","volume":"14","author":"H Imai","year":"1985","unstructured":"Imai, H., Iri, M., Murota, K.: Voronoi diagram in the laguerre geometry and its applications. SIAM J. Comput. 14(1), 93\u2013105 (1985)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9765_CR5","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/0216006","volume":"16","author":"F Aurenhammer","year":"1987","unstructured":"Aurenhammer, F.: Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16(1), 78\u201396 (1987)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9765_CR6","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF01901190","volume":"3","author":"D Avis","year":"1988","unstructured":"Avis, D., Bhattacharya, B.K., Imai, H.: Computing the volume of the union of spheres. Visual Comput. 3(6), 323\u2013328 (1988)","journal-title":"Visual Comput."},{"issue":"1","key":"9765_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/2049662.2049665","volume":"38","author":"F Cazals","year":"2011","unstructured":"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)","journal-title":"ACM Trans. Math. Softw."},{"key":"9765_CR8","doi-asserted-by":"crossref","unstructured":"Rycroft, C.: Voro++: A three-dimensional Voronoi cell library in C++ (2009)","DOI":"10.2172\/946741"},{"key":"9765_CR9","unstructured":"CGAL, Computational Geometry Algorithms Library. https:\/\/www.cgal.org"},{"key":"9765_CR10","unstructured":"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\u2013312. Society for Industrial and Applied Mathematics (2003)"},{"issue":"2\u20133","key":"9765_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.tcs.2008.08.006","volume":"408","author":"JD Boissonnat","year":"2008","unstructured":"Boissonnat, J.D., Wormser, C., Yvinec, M.: Anisotropic diagrams: Labelle Shewchuk approach revisited. Theor. Comput. Sci. 408(2\u20133), 163\u2013173 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"9765_CR12","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.comgeo.2004.02.006","volume":"33","author":"IZ Emiris","year":"2006","unstructured":"Emiris, I.Z., Karavelas, M.I.: The predicates of the Apollonius diagram: Algorithmic analysis and implementation. Comput. Geom. 33(1\u20132), 18\u201357 (2006)","journal-title":"Comput. Geom."},{"key":"9765_CR13","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.D., Wormser, C., Yvinec, M.: Curved voronoi diagrams. In: Effective Computational Geometry for Curves and Surfaces, pp 67\u2013116. Springer (2006)","DOI":"10.1007\/978-3-540-33259-6_2"},{"issue":"4","key":"9765_CR14","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1137\/S0036144599352836","volume":"41","author":"D Qiang","year":"1999","unstructured":"Qiang, D., Faber, V., Gunzburger, M.: Centroidal voronoi tessellations: applications and algorithms. SIAM Rev. 41(4), 637\u2013676 (1999)","journal-title":"SIAM Rev."},{"key":"9765_CR15","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.jcp.2016.07.007","volume":"322","author":"C Quan","year":"2016","unstructured":"Quan, C., Stamm, B.: Mathematical analysis and calculation of molecular surfaces. J. Comput. Phys. 322, 760\u2013782 (2016)","journal-title":"J. Comput. Phys."},{"key":"9765_CR16","volume-title":"Convex Analysis, Volume 28 of Princeton Mathematics Series","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis, Volume 28 of Princeton Mathematics Series. Princeton University Press, Princeton (1970)"},{"key":"9765_CR17","unstructured":"McCollum, F.: Power Diagrams (2014)"},{"key":"9765_CR18","volume-title":"NIST Handbook of Mathematical Functions Hardback and CD-ROM","author":"FWJ Olver","year":"2010","unstructured":"Olver, F.W.J.: NIST Handbook of Mathematical Functions Hardback and CD-ROM. Cambridge University Press, Cambridge (2010)"},{"key":"9765_CR19","unstructured":"Do Carmo, M.P., Do Carmo, M.P.: Differential Geometry of Curves and Surfaces, vol. 2. Prentice-Hall, Englewood Cliffs (1976)"},{"issue":"10","key":"9765_CR20","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1093\/bioinformatics\/18.10.1365","volume":"18","author":"J Brendan","year":"2002","unstructured":"Brendan, J, McConkey, VS, Edelman, M: Quantification of protein surfaces, volumes and atom\u2013atom contacts using a constrained Voronoi procedure. Bioinformatics 18(10), 1365\u20131373 (2002)","journal-title":"Bioinformatics"},{"issue":"suppl_1","key":"9765_CR21","first-page":"D393","volume":"37","author":"K Rother","year":"2008","unstructured":"Rother, K, Hildebrand, PW, Goede, A, Gruening, B, Preissner, R: Voronoia: Analyzing packing in protein structures. Nucleic Acids Res. 37(suppl_1), D393\u2013D395 (2008)","journal-title":"Nucleic Acids Res."},{"issue":"3","key":"9765_CR22","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00894-009-0541-y","volume":"16","author":"MS Till","year":"2010","unstructured":"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\u2013429 (2010)","journal-title":"J. Mol. Model."},{"key":"9765_CR23","doi-asserted-by":"crossref","unstructured":"Gerstein, M, Richards, F M: Protein geometry: Volumes areas and distances (2012)","DOI":"10.1107\/97809553602060000885"},{"issue":"7","key":"9765_CR24","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1093\/bioinformatics\/btw752","volume":"33","author":"F Cazals","year":"2016","unstructured":"Cazals, F, Dreyfus, T: The structural bioinformatics library: modeling in biomolecular science and beyond. Bioinformatics 33(7), 997\u20131004 (2016)","journal-title":"Bioinformatics"},{"issue":"5","key":"9765_CR25","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1107\/S0021889883010985","volume":"16","author":"ML Connolly","year":"1983","unstructured":"Connolly, M.L.: Analytical molecular surface calculation. J. Appl. Crystallogr. 16(5), 548\u2013558 (1983)","journal-title":"J. Appl. Crystallogr."},{"key":"9765_CR26","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.jmgm.2016.11.008","volume":"71","author":"C Quan","year":"2017","unstructured":"Quan, C., Stamm, B.: Meshing molecular surfaces based on analytical implicit representation. J. Molec. Graph. Modell. 71, 200\u2013210 (2017)","journal-title":"J. Molec. Graph. Modell."},{"key":"9765_CR27","unstructured":"Quan, C, Stamm, B: Molecular surface computation package. https:\/\/github.com\/quanchaoyu\/MolSurfComp"},{"key":"9765_CR28","unstructured":"Bium, H: A transformation for extracting new descriptions of shape. In: Symposium on Models for the Perception of Speech and Visual Form (1964)"},{"issue":"11","key":"9765_CR29","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1016\/j.cad.2004.01.011","volume":"36","author":"A Lieutier","year":"2004","unstructured":"Lieutier, A.: Any open bounded subset of rn has the same homotopy type as its medial axis. Comput. Aided Des. 36(11), 1029\u20131046 (2004)","journal-title":"Comput. Aided Des."}],"container-title":["Advances in Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-020-09765-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10444-020-09765-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-020-09765-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,30]],"date-time":"2023-09-30T19:09:51Z","timestamp":1696100991000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10444-020-09765-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,6]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["9765"],"URL":"https:\/\/doi.org\/10.1007\/s10444-020-09765-3","relation":{},"ISSN":["1019-7168","1572-9044"],"issn-type":[{"type":"print","value":"1019-7168"},{"type":"electronic","value":"1572-9044"}],"subject":[],"published":{"date-parts":[[2020,5,6]]},"assertion":[{"value":"20 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"44"}}