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 :
Communication dans un congrès
Sándor Fekete; Anna Lubiw. SoCG 2016, Jun 2016, Boston, United States. Proceedings of the 32nd International Symposium on Computational Geometry, 51, pp.10:1-10:16, 2016, LIPIcs
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01393017
Contributeur : Admin Upem <>
Soumis le : samedi 5 novembre 2016 - 18:24:39
Dernière modification le : jeudi 29 novembre 2018 - 16:32:04
Document(s) archivé(s) le : mardi 14 mars 2017 - 23:09:23

Fichier

LIPIcs-SoCG-2016-10.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01393017, version 1

Citation

Boris Aronov, Otfried Cheong, Michael Dobbins, Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. Sándor Fekete; Anna Lubiw. SoCG 2016, Jun 2016, Boston, United States. Proceedings of the 32nd International Symposium on Computational Geometry, 51, pp.10:1-10:16, 2016, LIPIcs. 〈hal-01393017〉

Partager

Métriques

Consultations de la notice

301

Téléchargements de fichiers

82