文章基本信息

标题：The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions
本地全文：下载
作者：Boris Aronov ; Otfried Cheong ; Michael Gene Dobbins 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：10:1-10:16
DOI：10.4230/LIPIcs.SoCG.2016.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We show that the union of translates of a convex body in three dimensional space can have a cubic number holes in the worst case, where a hole in a set is a connected component of its compliment. 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.
关键词：Union complexity; Convex sets; Motion planning