Chazelle polyhedron

The Chazelle polyhedron

Chazelle polyhedron is a non-convex polyhedron constructed by removing pieces of wedges from both top and bottom of a cube's sides, leaving the notches. Its saddle surface can be considered as the set of line segments that lie forming the hyperbolic paraboloid with an equation ${\displaystyle z=xy}$. ^[1] This polyhedron is named after Bernard Chazelle. ^[2]

Originally, the Chazelle polyhedron was intended to prove the quadratic lower bound of complexity on the decomposition of convex polyhedra in three dimensions. ^[1] The later applications are used regarding the problem related to the construction of lower bounds as in the binary space partition, ^[3] bounding volume hierarchy for collision detection, ^[4] decomposability of fat-polyhedra, ^[5] and optimal triangulation in mesh generation with its element's size. ^[6]

References

1. Si, Hang; Goerigk, Nadja (2016). "On Tetrahedralisations of Reduced Chazelle Polyhedra with Interior Steiner Points". Procedia Engineering. 163: 33–45. doi: 10.1016/j.proeng.2016.11.013 .
2. Chazelle, Bernard (1984). "Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm" . SIAM Journal on Computing. 13 (3): 488–507. doi:10.1137/0213031.
3. Paterson, Michael S.; Yao, F. Frances (1990). "Efficient binary space partitions for hidden-surface removal and solid modeling". Discrete & Computational Geometry. 5 (5): 485–503. doi:10.1007/BF02187806.
4. Erickson, Jeff (June 8–10, 2003). "Local polyhedra and geometric graphs". SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry. Association for Computing Machinery. pp. 171–180. doi:10.1145/777792.777820. ISBN   978-1-58113-663-0.
5. de Berg, Mark; Gray, Chris (2010). "Decompositions and boundary coverings of non-convex fat polyhedra". Computational Geometry. 43 (2): 73–83. doi:10.1016/j.comgeo.2009.04.003.
6. Bern, Marshall; Eppstein, David (1995). "Mesh Generation and Optimal Triangulation" . Computing in Euclidean Geometry. Lecture Notes Series on Computing. Vol. 4. pp. 47–123. doi:10.1142/9789812831699_0003. ISBN   978-981-02-1876-8.