Schönhardt polyhedron
Encyclopedia
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.
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 diagonal
s. 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 angle
s, forming a nonconvex polyhedron.
s, 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 diagonal
s of the polyhedron, but lie entirely outside the polyhedron.
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.
s, 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, constructed a polyhedron that shares with the Schönhardt polyhedron the property that it has no internal diagonal
s. 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 , although there exist non-manifold surfaces with no diagonals and any number of vertices greater than five .
to determine whether a non-convex polyhedron can be triangulated.
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, the Schönhardt polyhedron is the simplest non-convex
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
polyhedron
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
that cannot be triangulated into tetrahedra
Tetrahedron
In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...
without adding new vertices. It is named after German mathematician Erich Schönhardt
Erich Schönhardt
Erich Schönhardt was a German mathematician known for his 1928 discovery of the Schönhardt polyhedron, a non-convex polyhedron that cannot be partitioned into tetrahedra without introducing additional vertices.Schönhardt studied at the University of Stuttgart, and went on to do his graduate...
, who first described it in 1928.
Construction
The Schönhardt polyhedron can be formed by two congruentCongruence (geometry)
In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
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
Translation (geometry)
In Euclidean geometry, a translation moves every point a constant distance in a specified direction. A translation can be described as a rigid motion, other rigid motions include rotations and reflections. A translation can also be interpreted as the addition of a constant vector to every point, or...
of each other nor 180-degree reflections of each other.
The convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
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 diagonal
Diagonal
A diagonal is a line joining two nonconsecutive vertices of a polygon or polyhedron. Informally, any sloping line is called diagonal. The word "diagonal" derives from the Greek διαγώνιος , from dia- and gonia ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a...
s. 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 angle
Dihedral angle
In geometry, a dihedral or torsion angle is the angle between two planes.The dihedral angle of two planes can be seen by looking at the planes "edge on", i.e., along their line of intersection...
s, 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 angleDihedral angle
In geometry, a dihedral or torsion angle is the angle between two planes.The dihedral angle of two planes can be seen by looking at the planes "edge on", i.e., along their line of intersection...
s, 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 diagonal
Diagonal
A diagonal is a line joining two nonconsecutive vertices of a polygon or polyhedron. Informally, any sloping line is called diagonal. The word "diagonal" derives from the Greek διαγώνιος , from dia- and gonia ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a...
s of the polyhedron, but lie entirely outside the polyhedron.
Impossibility of triangulation
It is impossible to partition the Schönhardt polyhedron into tetrahedraTetrahedron
In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...
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 that the Schönhardt polyhedron can be generalized to other polyhedra, combinatorially equivalent to antiprismAntiprism
In geometry, an n-sided antiprism is a polyhedron composed of two parallel copies of some particular n-sided polygon, connected by an alternating band of triangles...
s, 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
Jessen's icosahedron
Jessen's icosahedron, sometimes called Jessen's orthogonal icosahedron is a non-convex polyhedron with the same number of vertices, edges and faces as the regular icosahedron...
, combinatorially equivalent to a regular icosahedron.
In a different direction, constructed a polyhedron that shares with the Schönhardt polyhedron the property that it has no internal diagonal
Diagonal
A diagonal is a line joining two nonconsecutive vertices of a polygon or polyhedron. Informally, any sloping line is called diagonal. The word "diagonal" derives from the Greek διαγώνιος , from dia- and gonia ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a...
s. The tetrahedron
Tetrahedron
In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...
and the Császár polyhedron
Császár polyhedron
In geometry, the Császár polyhedron is a nonconvex polyhedron, topologically a toroid, with 14 triangular faces.This polyhedron has no diagonals; every pair of vertices is connected by an edge. The seven vertices and 21 edges of the Császár polyhedron form an embedding of the complete graph K_7...
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
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
boundary) without diagonals , although there exist non-manifold surfaces with no diagonals and any number of vertices greater than five .
Applications
used Schönhardt's polyhedron as the basis for a proof that it is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
to determine whether a non-convex polyhedron can be triangulated.
External links
- Three Untetrahedralizable Objects, D. EppsteinDavid EppsteinDavid Arthur Eppstein is an American computer scientist and mathematician. He is professor of computer science at University of California, Irvine. He is known for his work in computational geometry, graph algorithms, and recreational mathematics.-Biography:Born in England of New Zealander...
. Includes a rotatable 3d model of the Schönhardt polyhedron.