The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

作者：Aronov Boris^*; Cheong Otfried; Dobbins Michael Gene; Goaoc Xavier

来源：Discrete & Computational Geometry, 2017, 57(1): 104-124.

DOI：10.1007/s00454-016-9820-4

• Union complexity
• Convex sets
• Motion planning

We show that the union of n translates of a convex body in R-3 can have Theta (n(3)) holes in the worst case, where a hole in a set X is a connected component of R-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.

• 出版日期2017-1