Peter Alfeld, --- Department of Mathematics, --- College of Science --- University of Utah

Rudin's Example of an Unshellable Triangulation

This is a non-technical description of shellability. For a more detailed description see my paper "Upper and Lower Bounds on the Dimension of Multivariate Spline Spaces" ( dvi file or postscript file ) which appeared in the SIAM J. on Numerical Analysis, v. 33, No. 2, pp. 571-588, April 1996.

A triangulation is a tessellation of a simply connected polygon by triangles such that no vertex of a triangle lies in the interior of an edge of another triangle. The higher dimensional analog of a triangle is a simplex. In three dimensional space a simplex is just a tetrahedron. In the plane a triangulation can always be built by starting with one triangle and then adding one triangle at a time so that at every step one has a set of triangles whose union forms a polygon that can be continuously deformed into a square (i.e., it's homeomorphic to a square). That seems pretty obvious.

However, it turns out (and came as a great surprise when it was first pointed out to me by Walter Whiteley) that in three-dimensional space the corresponding statement is not true. A triangulation that can be built by adding one simplex (tetrahedron) at a time such that at every step you have a collection of tetrahedra whose union is homeomorphic to a cube is called shellable. If a triangulation cannot be so built it is unshellable. The first example of an unshellable triangulation I came across is Rudin's Example. This is a tessellation of a tetrahedron by 41 smaller tetrahedra, sharing a total 14 vertices. If you remove any of the small tetrahedra you obtain something that is no longer homeomorphic to a cube. The key to understanding this fact is the observation that every one of the small tetrahedra has at least one vertex in the interior of one of the faces of the big tetrahedron---without having any other points in that face. So removing the tetrahedron creates points on the big tetrahedron where the face is "infinitely thin". I didn't understand Rudin's paper until I built the explorer map and actually looked at the triangulation.

But you want to see pictures! They follow. Just click on any of the little pictures to see an equivalent version with 64 times as many pixels. Unfortunately, to appreciate this example interactive manipulation to show the three dimensional structure is almost essential. But the pictures still give you the flavor of the object.

Here's the plain big tetrahedron: [image]

But it's really more complicated. [image] This is the same view, but with the individual small tetrahedra color coded by their index. The legend shows how the colors correspond to the indices of the 41 tetrahedra.

Perhaps it's easier to appreciate the complexity of this object by looking at a line drawing of it, from the same point of view as in the above two pictures. [image]

Or perhaps it helps to look at an exploded view of the triangulation (from a different view point) [image]

And another exploded view: [image]

Selected Literature

Return to Peter Alfeld's Home Page.

Last change: [14-Feb-1997]