Moser's Shadow Problem

Abstract

Moser's shadow problem asks to estimate the shadow function ${\mathfrak{s}}_b(n)$, which is the largest number such that for each bounded convex polyhedron $P$ with $n$ vertices in $3$-space there is some direction $\mathbf{v}$ (depending on $P$) such that, when illuminated by parallel light rays from infinity in direction $\mathbf{v}$, the polyhedron casts a shadow having at least ${\mathfrak{s}}_b(n)$ vertices. A general version of the problem allows unbounded polyhedra as well, and has associated shadow function ${\mathfrak{s}}_u(n)$. This paper presents correct order of magnitude asymptotic bounds on these functions. The bounded case has answer $\mathfrak{s}_b(n) = Θ\big( \log (n)/ (\log(\log (n))\big$. The unbounded shadow problem is shown to have the different asymptotic growth rate ${\mathfrak{s}}_u(n)=\Theta \left(1\right)$. Results on the bounded shadow problem follow from 1989 work of Chazelle, Edelsbrunner and Guibas on the (bounded) silhouette span number ${\mathfrak{s}}_b^{\ast }(n)$, defined analogously but with arbitrary light sources. We complete the picture by showing that the unbounded silhouette span number ${\mathfrak{s}}_u^{\ast }(n)$ grows as $\Theta (\log (n)/(\log (\log (n)))$.

v5, 25 pages, additional result added for unbounded silhouette span