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 [SUNY]
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
Document type :
Journal articles
Complete list of metadatas
https://hal-upec-upem.archives-ouvertes.fr/hal-01578460
Contributor : Xavier Goaoc <>
Submitted on : Tuesday, August 29, 2017 - 11:36:21 AM
Last modification on : Tuesday, August 13, 2019 - 11:08:11 AM

Licence

Distributed under a Creative Commons Attribution 4.0 International License

Links full text

arxiv

Identifiers

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

143

Contact

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