Finding the optimal shadows of a convex polytope

ABSTRACT

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 &Ogr;(nd-1) space and time to find the optimal placement. The other uses &Ogr(n) space to find the optimal placement in &Ogr;(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.

REFERENCES

• 1: [1] Edelsbrunner, H., Private communication.
• 2: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 3: [3] Edelsbrunner, H., O'Rourke, J., Seidel, R., "Constructing arrangements of lines and hyperplanes with applications", Proceedings of the 24th Foundations of Computer Science Conference, pp. 83-91, November 1983.
• 4: [4] Grunbaum, B., Convex polytopes, Wiley Interscience, 1967.
• 5: [5] Toussaint, G.T., "Solving geometric problems with the 'rotating calipers'", Proceedings of IEEE MELECON '83, Athens, Greece, May 1983.
• 6: [6] vanLeeuwen, J., Private communication.