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 GoaocConnect in order to contact the contributor Submitted on : Tuesday, August 29, 2017 - 11:36:21 AM Last modification on : Saturday, January 15, 2022 - 3:58:29 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⟩