The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions
Boris S. Aronov, Otfried Cheong, Michael Gene Dobbins, Xavier Goaoc · Discrete & Computational Geometry · 2016
We show that the union of n translates of a convex body in $$\mathbb {R}^3$$ can have $$\varTheta (n^3)$$ holes in the worst case, where a hole in a set X is a connected component of $$\mathbb {R}^3 \setminus X$$ . This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.