The Number of Holes in the Union of Translates of a Convex Set in Three DimensionsReportar como inadecuado




The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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





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

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



DESCARGAR PDF




Documentos relacionados