Union of Fat Objects in 3D

Definitions and mathematical statement

Fix a constant $\alpha\ge1$. A compact solid $K\subset\mathbb R^3$ is $\alpha$-fat in the radius-ratio sense when it contains a ball of radius $r>0$ and is contained in a ball of radius at most $\alpha r$. The centers need not coincide. For a precise main formulation, take convex semialgebraic solids specified by a fixed number of polynomial inequalities of bounded degree. These description bounds and $\alpha$ do not grow with the number of objects.

Given $n$ such objects $K_1,\ldots,K_n$, form $U=\bigcup_{i=1}^nK_i$. Its union complexity is the number of vertices, edges, and connected surface patches in the boundary subdivision induced by the input boundaries. Generic position can be imposed to avoid coincident boundary patches; it is the combinatorial boundary size that is counted, not volume or area.

Determine sharp worst-case bounds for this complexity. The source asks whether the appropriate general fat-object classes have near-quadratic complexity, meaning $O_\varepsilon(n^{2+\varepsilon})$ for every $\varepsilon>0$. Any theorem must specify its object class, description bound, and fatness convention: a radius ratio alone does not bound the complexity of an individual arbitrarily corrugated solid.

Short English statement

Find sharp bounds for the boundary complexity of unions of fat solid objects in three dimensions, with the object model and its description complexity fixed explicitly.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500004 (AMR-054-0004), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 4. Original source indexed by AMR-054-0004. https://topp.openproblem.net/p4.