The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Abstract

We show that the union of $n$ translates of a convex body in ${\mathbb{R}}^3$ can have $\Theta (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.

References in corpus (1)

• The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Cited by in corpus (1)

• The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions