@inproceedings{61ef6ffd9ea64d01ad2bde8b91ac10f5,
title = "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 ℝ3 can have Θ(n3) holes in the worst case, where a hole in a set X is a connected component of ℝ3 \ 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 = "Convex sets, Motion planning, Union complexity",
author = "Boris Aronov and Otfried Cheong and Dobbins, {Michael Gene} and Xavier Goaoc",
note = "Funding Information: B. Aronov is supported by NSF grants CCF-11-17336 and CCF-12-18791. O. Cheong is supported by NRF grant 2011-0030044 (SRC-GAIA) from the government of Korea. M. G. Dobbins is supported by NRF grant 2011-0030044 (SRC-GAIA) from the government of Korea.; 32nd International Symposium on Computational Geometry, SoCG 2016 ; Conference date: 14-06-2016 Through 17-06-2016",
year = "2016",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2016.10",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "10.1--10.16",
editor = "Sandor Fekete and Anna Lubiw",
booktitle = "32nd International Symposium on Computational Geometry, SoCG 2016",
}