{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T03:17:51Z","timestamp":1780975071420,"version":"3.54.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,11,1]],"date-time":"2011-11-01T00:00:00Z","timestamp":1320105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>\n            Balls and spheres are amongst the simplest 3\n            <jats:italic>D<\/jats:italic>\n            modeling primitives, and computing the volume of a union of balls is an elementary problem. Although a number of strategies addressing this problem have been investigated in several communities, we are not aware of any robust algorithm, and present the first such algorithm.\n          <\/jats:p>\n          <jats:p>Our calculation relies on the decomposition of the volume of the union into convex regions, namely the restrictions of the balls to their regions in the power diagram. Theoretically, we establish a formula for the volume of a restriction, based on Gauss' divergence theorem. The proof being constructive, we develop the associated algorithm. On the implementation side, we carefully analyse the predicates and constructions involved in the volume calculation, and present a certified implementation relying on interval arithmetic. The result is certified in the sense that the exact volume belongs to the interval computed.<\/jats:p>\n          <jats:p>Experimental results are presented on hand-crafted models illustrating various difficulties, as well as on the 58,898 models found in the tenth of July 2009 release of the Protein Data Bank.<\/jats:p>","DOI":"10.1145\/2049662.2049665","type":"journal-article","created":{"date-parts":[[2011,12,6]],"date-time":"2011-12-06T19:05:23Z","timestamp":1323198323000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Computing the volume of a union of balls"],"prefix":"10.1145","volume":"38","author":[{"given":"Frederic","family":"Cazals","sequence":"first","affiliation":[{"name":"INRIA Sophia-Antipolis-M\u00e9diterran\u00e9e, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Harshad","family":"Kanhere","sequence":"additional","affiliation":[{"name":"INRIA Sophia-Antipolis-M\u00e9diterran\u00e9e, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e9bastien","family":"Loriot","sequence":"additional","affiliation":[{"name":"INRIA Sophia-Antipolis-M\u00e9diterran\u00e9e, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,12,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00054-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00017-7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01901190"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/prot.22381"},{"key":"e_1_2_1_7_1","unstructured":"Br\u00f6nnimann H. Fabri A. Giezeman G.-J. Hert S. Hoffmann M. Kettner L. Schirra S. and Pion S. 2008. 2D and 3D geometry kernel. In CGAL User and Reference Manual 3.4 Ed. C. E. Board Ed.  Br\u00f6nnimann H. Fabri A. Giezeman G.-J. Hert S. Hoffmann M. Kettner L. Schirra S. and Pion S. 2008. 2D and 3D geometry kernel. In CGAL User and Reference Manual 3.4 Ed. C. E. Board Ed."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777845"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.10.004"},{"key":"e_1_2_1_10_1","unstructured":"Chazal F. Cohen-Steiner D. and M\u00e9rigot Q. 2007. Stability of boundary measure. res. rep. 6219 INRIA. http:\/\/hal.inria.fr\/inria-00154798.  Chazal F. Cohen-Steiner D. and M\u00e9rigot Q. 2007. Stability of boundary measure. res. rep. 6219 INRIA. http:\/\/hal.inria.fr\/inria-00154798."},{"key":"e_1_2_1_11_1","unstructured":"Cgal. Computational Geometry Algorithms Library. http:\/\/www.cgal.org.  Cgal. Computational Geometry Algorithms Library. http:\/\/www.cgal.org."},{"key":"e_1_2_1_12_1","unstructured":"CRLIBM. Correctly-rounded library of basic double-precision transcendental elementary functions. http:\/\/lipforge.ens-lyon.fr\/www\/crlibm\/links.html.  CRLIBM. Correctly-rounded library of basic double-precision transcendental elementary functions. http:\/\/lipforge.ens-lyon.fr\/www\/crlibm\/links.html."},{"key":"e_1_2_1_13_1","unstructured":"de Castro P. M. M. and Teillaud M. 2008. 3D spherical geometry kernel. In CGAL User and Reference Manual 3.4 ed. C. E. Board Ed.  de Castro P. M. M. and Teillaud M. 2008. 3D spherical geometry kernel. In CGAL User and Reference Manual 3.4 ed. C. E. Board Ed."},{"key":"e_1_2_1_14_1","volume-title":"Differential Geometry of Curves and Surfaces","author":"do Carmo M.","unstructured":"do Carmo , M. 1976. Differential Geometry of Curves and Surfaces . Prentice Hall , Englewood Cliffs, NJ . do Carmo, M. 1976. Differential Geometry of Curves and Surfaces. Prentice Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_15_1","volume-title":"Department of Computer Science","author":"Edelsbrunner H.","unstructured":"Edelsbrunner , H. 1992. Weighted alpha shapes. Tech. rep. UIUCDCS-R-92-1760 , Department of Computer Science , University Illinois , Urbana, IL . Edelsbrunner, H. 1992. Weighted alpha shapes. Tech. rep. UIUCDCS-R-92-1760, Department of Computer Science, University Illinois, Urbana, IL."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574053"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 2nd Library-Centric Software Design Conference. 75--84","author":"Fabri A.","unstructured":"Fabri , A. and Pion , S . 2006. A generic lazy evaluation scheme for exact geometric computations . In Proceedings of the 2nd Library-Centric Software Design Conference. 75--84 . Fabri, A. and Pion, S. 2006. A generic lazy evaluation scheme for exact geometric computations. In Proceedings of the 2nd Library-Centric Software Design Conference. 75--84."},{"key":"e_1_2_1_18_1","unstructured":"Gerstein M. and Richards F. 2001. Protein geometry: Volumes areas and distances. In The International Tables for Crystallography (Vol F Chap. 22) M. G. Rossmann and E. Arnold Eds. Springer 531--539. (Updated version of the 1977 paper.)  Gerstein M. and Richards F. 2001. Protein geometry: Volumes areas and distances. In The International Tables for Crystallography (Vol F Chap. 22) M. G. Rossmann and E. Arnold Eds. Springer 531--539. (Updated version of the 1977 paper.)"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2009.59"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.10.1365"},{"key":"e_1_2_1_21_1","volume-title":"Voronoia: Analyzing packing in protein structures. Nucleic Acids Res. 37 (Database issue, D3933).","author":"Rother K.","year":"2009","unstructured":"Rother , K. , Hildebrand , P. , Goede , A. , Gruening , B. , and Preissner , R . 2009 . Voronoia: Analyzing packing in protein structures. Nucleic Acids Res. 37 (Database issue, D3933). Rother, K., Hildebrand, P., Goede, A., Gruening, B., and Preissner, R. 2009. Voronoia: Analyzing packing in protein structures. Nucleic Acids Res. 37 (Database issue, D3933)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344940"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00894-009-0541-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1999.2829"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049662.2049665","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2049662.2049665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:41Z","timestamp":1750278401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049662.2049665"}},"subtitle":["A certified algorithm"],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["10.1145\/2049662.2049665"],"URL":"https:\/\/doi.org\/10.1145\/2049662.2049665","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}