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

Boris Aronov (1) , Otfried Cheong (2) , Michael Gene Dobbins (3) , Xavier Goaoc (4)

1 NYU Tandon School of Engineering
2 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]
3 Binghamton University [SUNY]
4 LIGM - Laboratoire d'Informatique Gaspard-Monge

We show that the union of n translates of a convex body in R³ can have Θ(n³) holes in the worst case, where a hole in a set X is a connected component of R³\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.

Mots clés: Convex sets; Union complexity; Motion planning

Domaines: Géométrie algorithmique [cs.CG]

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. SoCG 2016, Jun 2016, Boston, United States. pp.10:1-10:16. ⟨hal-01393017⟩