Union of Fat Objects in 3D

Let $n\in\mathbb{N}$ and consider $n$ objects in $\mathbb{R}^3$ . Assume that the objects are fat: the ratio of the circumradius of each object to its inradius is bounded. Determine the combinatorial complexity of their union as a function of $n$ . In particular, decide whether this complexity is nearly quadratic in $n$ .

Download

Abstract

An object in three-dimensional space is called fat when the ratio of its circumradius to its inradius is bounded. The open problem is to determine the combinatorial complexity of the union of $n$ such objects. This complexity is conjectured to be nearly quadratic in $n$ .

Background and progress

The origin of the problem is uncertain. Let $n\in\mathbb{N}$ denote the number of vertices or objects in the respective known results. The Minkowski sum of a polyhedron with $n$ vertices and the Euclidean unit ball has complexity $O(n^{2+\epsilon})$ [Agarwal and Sharir, 1999]. The same bound is known for the union of $n$ congruent cubes [Pach et al., 2001]. The source does not specify a range or quantifier for $\epsilon$ in these bounds.

In the plane, the union of fat objects has near-quadratic complexity [Efrat and Sharir, 2000]. It is widely believed that the same behavior holds in three dimensions, but the three-dimensional question remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p4.

Reference papers

Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensionsPankaj K. Agarwal, Micha SharirProc. 15th Annu. ACM Sympos. Comput. Geom. · 1999
On the complexity of the union of fat objects in the planeA. Efrat, Micha SharirDiscrete Comput. Geom. · 2000
The union of congruent cubes in three dimensionsJanos Pach, Ido Safruit, Micha SharirProc. 17th Annu. ACM Sympos. Comput. Geom. · 2001