finding the optimal shadows of a convex polytope
Let P be a convex polytope in R d . 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 &Ogr;( n d-1 ) space and time to find the optimal placement. The other uses &Ogr( n ) space to find the optimal placement in &Ogr;( n d -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 .
optimality shadow place lighting mean project normalization direct illumination algorithm placement space timing log