Computing Maximum-Area Sections of Convex Polyhedra
Introduction
Imagine a polyhedron of arbitrary shape and size. Suppose you could sweep a plane along some direction such that it passes completely through your polyhedron. As your plane moves through it, the boundary of the polyhedron creates a polygonal image or section on the moving plane. The problem we will address is as follows: Where should we position our plane such that the area of this polygonal section is maximised? And also, what is the maximum sectional area obtained in this way?
Sweeping a plane through a pentakisdodecahedron.
We'll formalise our problem as follows:
Let K be a convex polyhedron and let A(a) be the sectional area function of K (the area of the intersection between K and the plane x = a). Find the value of a that maximises A(a).
Note that we only allow convex polyhedra, as this significantly simplifies the problem. Also, we've formulated the problem such that the plane we sweep through our convex polyhedron must be perpendicular to the x-axis. If this seems a little restrictive, we can easily rotate our polyhedron such that the direction we are actually interested in lies along the x-axis.
In this online tutorial, we will, through definitions and background discussion, build up the theory needed to approach this problem. Afterwards, we'll present several algorithms of varying time complexities to solve it. We will also discuss some extensions to the problem, including applications. Finally, in the interactive Java applet, you can explore the properties of sections of convex polyhedra and find the maximum area sections and the sectional areas of arbitrary convex polyhedra.
This website is a project by Samuli Heilala for the course COMP 507, Computational Geometry, taught by Prof Godfried Toussaint at McGill University in fall 2005. It is based on a 1996 paper by Avis, Bose, Shermer, Snoeyink, Toussaint and Zhu [1].
Acknowledgements
The pentakisdodecahedron model is modified from a model on Wikipedia's 'Polyhedron' page. It is distributed under the GNU General Public License.
Next: Definitions.