NDLI: Computing the volume of a union of balls: A certified algorithm

Content Provider	ACM Digital Library
Author	Loriot, Sébastien Cazals, Frederic Kanhere, Harshad
Copyright Year	2011
Abstract	Balls and spheres are amongst the simplest $3\textit{D}$ 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. 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. 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.
Starting Page	1
Ending Page	20
Page Count	20
File Format	PDF
ISSN	00983500
e-ISSN	15577295
DOI	10.1145/2049662.2049665
Volume Number	38
Issue Number	1
Journal	ACM Transactions on Mathematical Software (TOMS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-12-07
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	α-shapes C++ design Computational geometry Van der Waals models Certified numerics Interval arithmetic Macro-molecular models Medial axis transform Protein modeling Structural biology Union of balls Volume calculation
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Computing the Volume of a Union of Balls: a Certified Algorithm

Computing the Volume of a Union of Balls: a Certified Algorithm

Algorithms for Complex Shapes with Certified Numerics and Topology Prototype implementation of certified approximation of the Medial Axis of smooth curves

Medial axis approximation of planar shapes from union of balls: a simpler and more robust algorithm.

Medial Axis Approximation of Planar Shapes from Union of Balls: A Simpler and more Robust Algorithm

2. Calculation of spectra of van der waals molecules (2000).

Accurate and Efficient Unions of Balls (2000)

Computing the exact arrangement of circles on a sphere, with applications in structural biology

Medial axis approximation from inner Voronoi balls: a demo of the Mesecina tool

Computing the volume of a union of balls: A certified algorithm

Similar Documents

Computing the Volume of a Union of Balls: a Certified Algorithm

Computing the Volume of a Union of Balls: a Certified Algorithm

Algorithms for Complex Shapes with Certified Numerics and Topology Prototype implementation of certified approximation of the Medial Axis of smooth curves

Medial axis approximation of planar shapes from union of balls: a simpler and more robust algorithm.

Medial Axis Approximation of Planar Shapes from Union of Balls: A Simpler and more Robust Algorithm

2. Calculation of spectra of van der waals molecules (2000).

Accurate and Efficient Unions of Balls (2000)

Computing the exact arrangement of circles on a sphere, with applications in structural biology

Medial axis approximation from inner Voronoi balls: a demo of the Mesecina tool

Computing the volume of a union of balls: A certified algorithm