 | ||
In geometry, the Schönhardt polyhedron is the simplest non-convex polyhedron that cannot be triangulated into tetrahedra without adding new vertices. It is named after German mathematician Erich Schönhardt, who first described it in 1928.
Contents
Construction
The Schönhardt polyhedron can be formed by two congruent equilateral triangles in two parallel planes, such that the line through the centers of the triangles is perpendicular to the planes. The two triangles should be twisted with respect to each other, so that they are neither translates of each other nor 180-degree reflections of each other.
The convex hull of these two triangles forms a convex polyhedron that is combinatorially equivalent to a regular octahedron; along with the triangle edges, it has six edges connecting the two triangles to each other, with two different lengths, and three interior diagonals. The Schönhardt polyhedron is formed by removing the longer of the three connecting edges, and replacing them by the three diagonals of the convex hull.
Alternatively, the Schönhardt polyhedron can be formed by removing three disjoint tetrahedra from this convex hull: each of the removed tetrahedra is the convex hull of four vertices from the two triangles, two from each triangle. This removal causes the longer of the three connecting edges to be replaced by three new edges with concave dihedral angles, forming a nonconvex polyhedron.
Properties
The Schönhardt polyhedron is combinatorially equivalent to the regular octahedron: its vertices, edges, and faces can be placed in one-to-one correspondence with the features of a regular octahedron. However, unlike the regular octahedron, three of its edges have concave dihedral angles, and these three edges form a perfect matching of the graph of the octahedron; this fact is sufficient to show that it cannot be triangulated.
The six vertices of the Schönhardt polyhedron can be used to form fifteen unordered pairs of vertices. Twelve of these fifteen pairs form edges of the polyhedron: there are six edges in the two equilateral triangle faces, and six edges connecting the two triangles. The remaining three edges form diagonals of the polyhedron, but lie entirely outside the polyhedron.
Impossibility of triangulation
It is impossible to partition the Schönhardt polyhedron into tetrahedra whose vertices are vertices of the polyhedron. More strongly, there is no tetrahedron that lies entirely inside the Schönhardt polyhedron and has vertices of the polyhedron as its four vertices. For, among any four vertices of the Schönhardt polyhedron, at least one pair of vertices from these four vertices must be a diagonal of the polyhedron, which lies entirely outside the polyhedron.
Related constructions
It was shown by Rambau (2005) that the Schönhardt polyhedron can be generalized to other polyhedra, combinatorially equivalent to antiprisms, that cannot be triangulated. These polyhedra are formed by connecting regular k-gons in two parallel planes, twisted with respect to each other, in such a way that k of the 2k edges that connect the two k-gons have concave dihedrals. Another polyhedron that cannot be triangulated is Jessen's icosahedron, combinatorially equivalent to a regular icosahedron.
In a different direction, Bagemihl (1948) constructed a polyhedron that shares with the Schönhardt polyhedron the property that it has no internal diagonals. The tetrahedron and the Császár polyhedron have no diagonals at all: every pair of vertices in these polyhedra forms an edge. It remains an open question whether there are any other polyhedra (with manifold boundary) without diagonals (Ziegler 2008), although there exist non-manifold surfaces with no diagonals and any number of vertices greater than five (Szabó 1984, 2009).
Applications
Ruppert & Seidel (1992) used Schönhardt's polyhedron as the basis for a proof that it is NP-complete to determine whether a non-convex polyhedron can be triangulated.