[Math] What can be said about the Shadow hull and the Sight hull

computational geometrygeometrymg.metric-geometry

This is a question implicitly raised by Is the sphere the only surface all of whose projections are circles? Or: Can we deduce a spherical Earth by observing that its shadows on the Moon are always circular?.

Suppose $X$ is a closed subset of $\mathbb R^n$.

What can you say about

  1. The shadow hull of $X$: the intersection of complements of lines disjoint from $X$, and

  2. The sight hull: the intersection of complements of rays disjoint from $X$?

Do these sets have standard mathematical or computer graphics / computational geometry names?
Are there other good characterizations?
How hard are they to compute (say for a polyhedron, so that complexity is fairly well-defined)?

Note: two sets with the same shadow hull cast the same shadows (in light cast by any parallel beam). Two sets with the same sight hull have the same visible surface. Sight hull $\subset$ shadow hull $\subset$ convex hull.

Addendum While we're at it: one could also define the "Knife Hull" to be the intersection of complements of half-planes disjoint from the set. In other words, it's the best outer approximation of a small shape that you can carve using a long wide straight-edged knife. This makes it sight hull $\subset$ shadow hull $\subset$ knife hull $\subset$ convex hull.

All of these are invariant under affine transformations.

Best Answer

A very partial answer, just mentioning one reference, and one additional result (w/o a reference). Nina Amenta and Günter Ziegler computed the combinatorial complexity of 2D shadows (and $k$-shadows) of convex polytopes in $\mathbb{R}^d$ in their now heavily cited 1999 paper "Deformed Products and Maximal Shadows of Polytopes" (Advances in Discrete and Computational Geometry 233:57-90 (1999)). They showed that a polytope of $n$ facets can have $\Theta(n^{\lfloor d/2 \rfloor})$ vertices in its 2D shadow, for fixed $d$—surprisingly large. $k$-dimensional shadows have various applications to robotics and computer vision. For example, the set of stable 3-finger friction grasps of a polygon can be represented as a 3-shadow of a 5-polytope.

I have seen your "shadow hull" called the line hull. I cannot provide a reference, but I do know that Sergei Bespamyatnikh constructed a (nonconvex) 3D polyhedron of $n$ vertices whose line hull has combinatorial complexity $\Theta(n^9)$.

Added. The shadow hull is called the visual hull in the computer vision literature. A. Laurentini, "The Visual Hull Concept for Silhouette-Based Image Understanding" IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 16, Issue 2 (February 1994) pp. 150 - 162. From the Abstract: "it is the maximal object silhouette-equivalent to $S$, i.e., which can be substituted for $S$ without affecting any silhouette."

Related Question