The number of holes in the union of translates of a convex set in three dimensions (Q512258)

An important conjecture in computational geometry states that the complexity of the union of \(n\) objects in \(3\)-dimensional Euclidean space has at most nearly quadratic complexity. A weaker version of this conjecture states that the same upper bound holds for the number of connected components of the complement of the union, in the special case that the objects are translates of a given convex body in \(3\)-space. The authors of this paper disprove the latter conjecture. More specifically, they construct a convex body \(K\) and \(3m\) translates of \(K\) whose union has \(\Theta(m^3)\) holes. Their proof is based on constructing, for every value of \(m\), a convex polytope \(K_m\) with \(\Theta(m^2)\) faces, and \(3m\) translates of \(K_m\) whose union has \(\Theta(m^3)\) holes, and then applying a limiting argument. They point out applications to motion planning, and also to the number of vertices of the Voronoi diagram of \(n\) points in \(3\)-space, with respect to a given convex distance function.