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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01393017
Contributor : Admin Upem <>
Submitted on : Saturday, November 5, 2016 - 6:24:39 PM
Last modification on : Tuesday, August 13, 2019 - 11:08:11 AM
Long-term archiving on : Tuesday, March 14, 2017 - 11:09:23 PM

File

LIPIcs-SoCG-2016-10.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • 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. SoCG 2016, Jun 2016, Boston, United States. pp.10:1-10:16. ⟨hal-01393017⟩

Share

Metrics

Record views

357

Files downloads

211