Determining the convexity of polyhedra is a terrible task, best left to llamas and emus, who toil religiously in order to alleviate our convexity connundrums. This group of pages is designed to show an interesting and efficient way to determine whether a given polyhedra (in 3 dimensions, or even more!) is convex, and includes a Java applet which allows you to give it a reasonable input (a polyhedra) and see how the algorithm works on that input. If you have any comments or suggestions for the pages, please pass them along, and I'll try to remedy them.

What's a polytope? Following the definitions given in the paper this site is based upon, if you can imagine a polyhedron as being a bunch of lines and points in space that surround a region, a polytope is the region which is surrounded. I'll generally be referring to things as polygons and polyhedrons, but sometimes polytope slipped in there, don't worry too hard, just think of it as being a region in 3D space bounded by the polyhedron.

For the uninitiated, a brief detour into an idea of convexity might be in order. We consider a polygon to be convex, among other classifications, if for any two points in the polygon, we can draw a straight line between them that lies entirely inside the polygon. For example a triangle is convex, because for any two points in the triangle, the line connecting those points will also be in the triangle. A 5 pointed star polygon however, would not be convex, because if you took points in adjacent fingers of the star, the line between them would not be completely within the star.

The polygon on the left is convex, any line joining two points in the interior of the polygon will also be completely within the polygon. The polygon on the right is not convex, as we can see that the line joining the two points inside the polygon is not completely within the polygon.

This same principle can be applied in higher dimensions. In 3D, inside of a region on the plane, we now have a volume in space, and if we take any two points in the volume on the interior of the polyhedron, the line connecting them has to remain completely within the volume of the polyhedron. For example, a cube is a convex polyhedron, whereas a bow tie shaped polyhedron would not be:

The polyhedron (a cube) on the left is a convex polyhedron: the line between any two points on the interior of the polyhedron will be completely in the interior (kernel) of the polyhderon. The polyhedron on the right is not, as there exist points (the red ones for example) for which this is not true.

Melhorn et al came up with a way to check whether a locally convex polyhedron is the boundary of a convex polytope by first computing a point q of the interior of the polygon or polyhedron and a ray r emanating from q and passing through the centroid of an artibrarily chosen facet, and then checking that no other facet is intersected by r. The simplified version of this, is that we choose a point inside the region, and then send a ray out from that point, it will intersect only one facet. If we check every facet, we can be assured our polyhedron is convex. Their algorithm runs in linear time with respect to the number of verticies, which is optimal for this problem.

Rays emanating from an arbitrary point in the kernel of G.

Our plucky team of Devillers, Liotta, Preparata, and Tamassia have come up with another interesting way of checking the convexity of a polytope. It uses properties of special edges called seam edges to allow the checking of convexity in linear time, for any dimension. Don't worry if it's a little bit confusing at first, things make more sense after you've seen some diagrams. The goal of the algorithm is to check whether a given graph (vertices and edges) and an ordering of the graph is the boundary of a convex region. If you're ready to go, the best place to start is the definitions.