Visibility complex of disjoint unit spheres

Definitions and mathematical statement

Let $B_i=\{x\in{\mathbb{R}}^3:\|x-c_i\|\le1\}$, $1\le i\le n$. Under the opaque-solid interpretation of the source's unit spheres, pairwise disjointness is $\|c_i-c_j\|>2$ for $i\ne j$. The objects have equal fixed radius, not arbitrary radii. The problem asks for the worst-case combinatorial complexity, as a function of $n$, of their three-dimensional visibility complex.

The visibility complex is not defined in the extracted statement. In its usual geometric setting it organizes maximal free straight line segments, possibly unbounded, in the complement of the obstacles, including strata where tangencies occur; it is not simply the graph recording which pairs of spheres see each other. A precise extremal target, once the intended complex and cell-count convention are supplied, is \[ C(n)=\sup_{\substack{c_1,\ldots,c_n\in{\mathbb{R}}^3\\ \|c_i-c_j\|>2\ (i\ne j)}} \sum_{k\ge0}f_k\left(\mathcal V(B_1,\ldots,B_n)\right), \] where $f_k$ counts the $k$-dimensional cells of that specified complex. Determine matching asymptotic upper and lower bounds for $C(n)$. This formula makes a common total-cell interpretation explicit; it does not supply the absent definition of $\mathcal V$. The source must clarify whether it counts all cells or a particular dimension, how free segments and tangent contacts are identified, and whether degeneracies are included or general position is assumed.

The supplied research summary conservatively reports partial progress and no verified tight bound for disjoint unit spheres. It mentions work on the three-dimensional visibility complex for more general scenes without giving numerical bounds that could be specialized here.

Short English statement

Find tight worst-case bounds for the size of the visibility complex of $n$ pairwise disjoint unit spheres in ${\mathbb{R}}^3$. The precise complex, counting convention, and treatment of degeneracies require the source definition.

Sources

• Local UnsolvedMath registry, permanent ID $3800010$, exact source code catalogue entry, "Visibility complex of disjoint unit spheres." Proposer field: Jeff Erickson and cited proposers.
• Erickson, Open Problems in Computational Geometry, item with that title; https://jeffe.cs.illinois.edu/open/. HTML extraction, recorded access 2026-07-29.
• Durand, Drettakis and Puech, "The 3D visibility complex" (1997), as cited in the supplied research summary for general scenes. The record supplies no venue, precise theorem, or explicit unit-sphere bounds.