Schönhardt polyhedron

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.

The Schönhardt polyhedron.
3D model of the Schönhardt polyhedron

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 three longest connecting edges, and replacing them by the three diagonals of the convex hull. An equivalent procedure is to start with a regular octahedron and twist one face within its plane, without breaking any edges. With a 60° twist a triangular prism is formed; with a 120° twist there are two tetrahedra sharing the central vertex; any amount of twist between these two cases gives a Schönhardt polyhedron.

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.

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.

gollark: I think it could be done with raycasting but it'd be vulnerable to the player moving too fast or teleporting.
gollark: Maybe enslaved skeletons. But they're hard to manage because disableAI doesn't work.
gollark: I see. Troubling. I don't think we can make bow sentries work at all.
gollark: We should discuss something more important, like what a great idea it is to buy [HG]Tech™ bee products at excellent prices.
gollark: Fail violently, I mean.

References
  • Bagemihl, F. (1948), "On indecomposable polyhedra", American Mathematical Monthly, 55 (7): 411–413, doi:10.2307/2306130, JSTOR 2306130
  • Rambau, J. (2005), "On a generalization of Schönhardt's polyhedron" (PDF), in Goodman, Jacob E.; Pach, János; Welzl, Emo (eds.), Combinatorial and Computational Geometry, MSRI Publications, 52, Cambridge: Cambridge University Press, pp. 501–516
  • Ruppert, J.; Seidel, R. (1992), "On the difficulty of triangulating three-dimensional nonconvex polyhedra", Discrete & Computational Geometry, 7: 227–253, doi:10.1007/BF02187840
  • Schönhardt, E. (1928), "Über die Zerlegung von Dreieckspolyedern in Tetraeder", Mathematische Annalen, 98: 309–312, doi:10.1007/BF01451597
  • Szabó, Sándor (1984), "Polyhedra without diagonals", Periodica Mathematica Hungarica, 15 (1): 41–49, doi:10.1007/BF02109370
  • Szabó, Sándor (2009), "Polyhedra without diagonals II", Periodica Mathematica Hungarica, 58 (2): 181–187, doi:10.1007/s10998-009-10181-x
  • Ziegler, Günter M. (2008), "Polyhedral surfaces of high genus", in Bobenko, A. I.; Schröder, P.; Sullivan, J. M.; et al. (eds.), Discrete Differential Geometry, Oberwolfach Seminars, 38, Springer-Verlag, pp. 191–213, arXiv:math/0412093, doi:10.1007/978-3-7643-8621-4_10, ISBN 978-3-7643-8620-7, math.MG/0412093
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.