# What can be said about the Shadow hull and the Sight hull?

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

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.

• @Bill: I am also interested in what I have been calling (to myself!) the drip hull, the enclosing shape that cannot hold water in any orientation. Maybe this needs a separate posting... – Joseph O'Rourke Sep 18 '10 at 19:38
• Why do you say that the shadow hull is contained in the sight hull? Consider a hollow cone without base. The shadow hull should be a solid cone (the convex hull), since no point in the "interior" of the cone lies on a line disjoint from the cone. But the sight hull will just be the hollow cone again, since any point in the interior lies on a ray disjoint from the cone. – Tom Church Sep 18 '10 at 20:10
• Right, I wrote it backward, confounding the set and its complement. Thanks --- I'll edit and fix it. – Bill Thurston Sep 18 '10 at 20:33

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."