Finding the optimal shadows of a convex polytope
Michael S. McKenna, Raimund Seidel · 1985
Let P be a convex polytope in Rd. We discuss the problem of placing a light source at infinity so as to minimize or maximize the shadow area of the polytope. By shadow area we mean the (d-1)-volume of the orthogonal projection of P on a hyperplane normal to the direction of illumination. Let n be the number of (d-1)-dimensional facets of the polytope. We exhibit two algorithms for finding the optimal placement of the light source. One algorithm uses O(nd-1) space and time to find the optimal placement. The other uses O(n) space to find the optimal placement in O(nd-1 log n) time. Also, we present an interesting result relating the minimum and maximum shadow areas of P to the radii of the inscribed and circumscribed sphere of a zonotope derived from P.