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: Union complexity; Convex sets; 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. Discrete and Computational Geometry, 2017, 57 (1), pp.104 - 124. ⟨10.1007/s00454-016-9820-4⟩. ⟨hal-01578460⟩