17
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ @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... $\endgroup$ Commented Sep 18, 2010 at 19:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tom Church
    Commented Sep 18, 2010 at 20:10
  • $\begingroup$ Right, I wrote it backward, confounding the set and its complement. Thanks --- I'll edit and fix it. $\endgroup$ Commented Sep 18, 2010 at 20:33

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Thanks for digging up the references. It would be a mistake to start trying to perpetrate new names, except in circumstances where existing terminology isnot established or is clearly deficient compared to what it might be replaced with. $\endgroup$ Commented Sep 20, 2010 at 11:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .