Untetrahedralizable Objects (original) (raw)

Schönhardt Polyhedron This shape was described by E. Schönhardt, "Über die Zerlegung von Dreieckspolyedern in Tetraeder", _Math. Annalen_98 (1928) 309-312. It is combinatorially an octahedron, twisted so that three of its dihedrals are concave. Each vertex is connected by edges to four others, but the diagonal to the remaining vertex always passes outside the polyhedron, so there is no way to place a diagonal inside partitioning the shape into tetrahedra.One consequence is that, although the region CH(P u Q)-(P u Q) between two convex polyhedra P and Q can always be tetrahedralized [J. E. Goodman and J. Pach, "Cell decomposition of polytopes by bending",Israel J. Math. 64 (1988) 129-138], the region between three cannot (the Schönhardt polyhedron can be expressed as the region between three tetrahedra).	Thurston Polyhedron This shape (not the colored blocks, but the region of space surrounding them) was used by M. S. Paterson and F. F. Yao, "Binary partitions with applications to hidden-surface removal and solid modeling", Proc. 5th ACM Symp. Comp. Geom. (1989) 23-32, to show a lower bound on the complexity of subdividing an axis-parallel polyhedron into convex regions. Three sets of cuboids interlace to surround Omega(_n_3/2) cubical voids, each of which must occupy a separate component in any convex decomposition. The point in the center of each void can not see any vertices, so the shape is untetrahedralizable.Paterson and Yao credit this application of the shape to a personal communication by W. P. Thurston, but the shape itself has been seen before e.g. in Alan Holden's book Shapes, Space, and Symmetry (Columbia Univ. Press 1971) p. 161. Holden also describes a related interlocked lattice of triangular prisms with rhombic-dodecahedron voids.	Chazelle Polyhedron This shape is formed by removing wedges from a cube. The upper wedges have their edges on lines of the form_y_ = xz + epsilon,z = const and the lower wedges have their edges on lines of the form_y_ = xz - epsilon,x = const, so the hyperboloid y = xz is approximated on one side by ridges parallel to the xy plane, and on the other side by ridges parallel to the yz plane.B. Chazelle, "Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm", SIAM J. Comput. 13 (1984) 488-507, showed that this example can not be partitioned into fewer than Omega(_n_2) convex pieces. As I pointed out to Paterson and Yao, this same example solves an open problem from their paper on the complexity of three-dimensional binary space partitions.

Last update: .