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 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.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2017, 57 (1), pp.104 - 124. 〈https://link.springer.com/article/10.1007/s00454-016-9820-4〉. 〈10.1007/s00454-016-9820-4〉
Liste complète des métadonnées

https://hal-upec-upem.archives-ouvertes.fr/hal-01578460
Contributeur : Xavier Goaoc <>
Soumis le : mardi 29 août 2017 - 11:36:21
Dernière modification le : vendredi 13 juillet 2018 - 14:34:04

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Lien texte intégral

Identifiants

Citation

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. 〈https://link.springer.com/article/10.1007/s00454-016-9820-4〉. 〈10.1007/s00454-016-9820-4〉. 〈hal-01578460〉

Partager

Métriques

Consultations de la notice

97