Abstract : We show that the union of n translates of a convex body in R3 can have Θ(n3) holes in the worst case, where a hole in a set X is a connected component of R3\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.
https://hal-upec-upem.archives-ouvertes.fr/hal-01578460
Contributor : Xavier Goaoc
<>
Submitted on : Tuesday, August 29, 2017 - 11:36:21 AM
Last modification on : Tuesday, August 13, 2019 - 11:08:11 AM
Licence
Distributed under a Creative Commons Attribution 4.0 International License
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, Springer Verlag, 2017, 57 (1), pp.104 - 124. ⟨10.1007/s00454-016-9820-4⟩. ⟨hal-01578460⟩
