Enumeration of Non-Convex Polyhedra

And what do we mean by "non-convex" polyhedron anyway?

Steven Dutch, Natural and Applied Sciences, University of Wisconsin - Green Bay

Convex polyhedra are mathematically neat. You have three or more faces meeting at each vertex. The faces are always convex themselves, and any network of faces that can be drawn on a plane can be built in three dimensions as a polyhedron. Picture drawing the net on a flattened balloon, then inflating it. They're easy to define and the rules are unambiguous. Non-convex polyhedra are hard to define and even harder to enumerate. Do we allow non-convex faces? What about faces with holes? Can the polyhedron have holes, that is, be a toroid? There is tons of research on non-convex polyhedra because of the need to approximate surfaces as nets of triangles for computer animation, but nobody seems to have tried to enumerate them.

Triangles are always convex, therefore, there can be no non-convex tetrahedra. The simplest non-convex polyhedron seems to be the one below. It can be visualized as a tetrahedron with the base dimpled inward to make a dart-shaped polygon. However, we can smoothly deform the base outward to make it a convex quadrilateral, so this solid is topologically equivalent to a square pyramid. It seems obvious that any non-convex polyhedron with only convex faces can be deformed into a convex polyhedron. So this polyhedron is actually pretty trivial apart from being the minimal non-convex case.

 Another five-sided non-convex polyhedron is shown at left. Here, a tetrahedron face is creased across its width and folded inward. This solid consists of two triangles not in contact and three quadrilaterals between them. It's topologically equivalent to a triangular prism, the other convex pentahedron.
The simplest irreducibly non-convex polyhedron seems to be the one below, created by notching the edge of a tetrahedron. It can't be smoothly transformed into a convex polyhedron, and in fact it has something no convex polyhedron can have: two faces meeting at non-consecutive vertices. A slight variation, created by notching only a part of an edge, results in faces meeting along two edges, or alternatively, having an interrupted edge. If we were to try to eliminate the ambiguity by making the two edge segments non-intersecting, we'd either have to accept non-coplanar faces, or add additional edges.

We can obviously apply this gimmick to the edges of any convex polyhedron, so this, too, results in fairly trivial cases.

The simplest possible toroids have seven faces. There's a really fascinating one (to be discussed below) but you don't need to get fancy. Take a tetrahedron (the simplest possible solid) and punch a triangular hole in it (the simplest possible hole). If you punch through the middles of faces, you end up with faces with holes. Do we want that?

A face is said to be simply connected if a path between two points on the face can be deformed into any other path without being broken. Obviously a face with a hole is not simply connected because a path on one side of the hole can't be deformed into a path passing on the other side without breaking it. It seems like a good idea to stick to simply connected faces. A solid where any path between two interior points can be deformed into any other path is also simply connected. A solid need not be convex to be simply connected. A toroid is not simply connected but a toroid can still have only simply connected faces.

 By making the hole large enough, we can divide faces into separate regions joined only at vertices. In the case shown here, the tunnel tapers toward the opposite vertex, so that only one face is cut into separate regions. Do we count those as a single face or as multiple faces? In most polyhedron studies, all coplanar face segments are considered a single face.

If we punch the hole from one edge to the opposite edge, we avoid faces with holes. An example is shown at left below. On the right, the hole touches an edge of the tetrahedron, another complication of toroidal polyhedra.

Easily the most remarkable toroid with seven faces is the Szilassi polyhedron, shown below. It has the remarkable property that every face touches every other face, demonstrating that seven colors are necessary on a torus (a result, remarkably, that was proven long before the seemingly simpler four-color problem was solved for the plane). Unfortunately, none of the toroids that result from punching holes in tetrahedra have that property. Although all the faces of the Szlassi polyhedron are only hexagons, they are remarkably complex. Unlike all the previous examples, this polyhedron isn't derived from simple modifications of convex polyhedra. Even though the toroid itself is not simply connected, all its faces are.

The toroid below seems to be the simplest "conventional" toroidal polyhedron. It consists of three triangular prisms linked into a ring. It can't be simply derived by modifying some other polyhedron, and all the faces are convex. Most illustrations show the prisms pointing inward, but they can also point outward.

All periodic plane tesselations can be rolled into a cylinder, which can then be bent into a torus, so every plane tesselation can be the basis for a toroidal polyhedron. The toroid above is simply a quadrilateral tesselation bent into a torus.