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 [State University of New York]
4 LIGM - Laboratoire d'Informatique Gaspard-Monge
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.
Keywords : Union complexity Convex sets Motion planning
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 : jeudi 29 novembre 2018 - 16:32:04

Licence

Distributed under a Creative Commons Paternité 4.0 International License

Lien texte intégral

arxiv

Identifiants

Collections

UPEC-UPEM | LIGM_MOA | ENPC | PARISTECH | LIGM | ESIEE-PARIS

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

105

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD