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 : mercredi 11 avril 2018 - 12:12:03

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Lien texte intégral

Identifiants

Collections

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

87