The Number of Holes in the Union of Translates of a Convex Set in Three DimensionsReport as inadecuate




The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions - Download this document for free, or read online. Document in PDF available to download.

1 New York University Tandon School of Engineering 2 KAIST - Department of Electrical Engineering Korea Advanced Institute of Science and Technology 3 Binghamton University 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





Author: Boris Aronov - Otfried Cheong - Michael Dobbins - Xavier Goaoc -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents