Union volume calculation of translated convex shapes differs by dimension
Union of Translates of a Convex Body
Computational Geometry
Summary
The paper looks at how to compute the combined volume of several copies of a convex shape moved around in space. For round shapes like balls, the calculation can be simplified by focusing on special areas called Voronoi cells, but this shortcut only fully works in one or two dimensions for all convex shapes. In three dimensions, the authors show that this simplification technique only holds when the shape is an ellipsoid, a rounded shape like a stretched or squished ball.
What this means in practice
- •For computer graphics developers: Optimize volume calculations of moving convex shapes in 2D rendering by prioritizing Voronoi diagram intersections.
- •For geometric algorithm designers: Focus exact 3D volume union methods on ellipsoids and develop alternatives for other convex shapes due to proven limitations.
A theory result. No direct application yet.
Authors
Alec Shelley, Daniel Tartakovsky
Abstract
We consider the problem of calculating the volume of the union of translates of a strictly convex body $K\subset\mathbb{R}^d$. When $K$ is a ball, it is possible to simplify the inclusion-exclusion formula by summing over only a small subset of all terms. This subset corresponds to intersecting cells in the Voronoi diagram of the ball centers. We prove that the same simplification is valid for every strictly convex $K$ if and only if $d\leq 2$. Moreover, in three dimensions and when $K$ is $C^4$, we use the Fubini-Pick affine invariant to show that the topological identity underlying this technique holds if and only if $K$ is an ellipsoid.