Chazelle polyhedron
{{Short description|A cube with notched surfaces}}
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 .{{cite journal
| last1 = Si | first1 = Hang
| last2 = Goerigk | first2 = Nadja
| title = On Tetrahedralisations of Reduced Chazelle Polyhedra with Interior Steiner Points
| url = https://www.sciencedirect.com/science/article/pii/S1877705816333173
| journal = Procedia Engineering
| volume = 163
| year = 2016
| pages = 33–45
| doi = 10.1016/j.proeng.2016.11.013
| doi-access = free
}} This polyhedron is named after Bernard Chazelle.{{cite journal
| last = Chazelle | first = Bernard | author-link = Bernard Chazelle
| journal = SIAM Journal on Computing
| volume = 13 | issue = 3 | year = 1984
| title = Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
| pages = 488–507 | url = https://epubs.siam.org/doi/abs/10.1137/0213031
| doi = 10.1137/0213031
}}
Originally, the Chazelle polyhedron was intended to prove the quadratic lower bound of complexity on the decomposition of convex polyhedra in three dimensions. The later applications are used regarding the problem related to the construction of lower bounds as in the binary space partition,{{cite journal
| url = https://link.springer.com/article/10.1007/BF02187806
| title = Efficient binary space partitions for hidden-surface removal and solid modeling
| journal = Discrete & Computational Geometry
| volume = 5 | pages = 485–503 | year = 1990
| doi = 10.1007/BF02187806
| last1 = Paterson
| first1 = Michael S.
| last2 = Yao
| first2 = F. Frances
| issue = 5
}} bounding volume hierarchy for collision detection,{{cite conference
| last = Erickson | first = Jeff
| title = SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry
| date = June 8–10, 2003
| pages = 171–180
| contribution = Local polyhedra and geometric graphs
| contribution-url = https://dl.acm.org/doi/abs/10.1145/777792.777820
| doi = 10.1145/777792.777820
| publisher = Association for Computing Machinery
| isbn = 978-1-58113-663-0
}} decomposability of fat-polyhedra,{{cite journal
| last1 = de Berg | first1 = Mark
| last2 = Gray | first2 = Chris
| title = Decompositions and boundary coverings of non-convex fat polyhedra
| url = https://www.sciencedirect.com/science/article/pii/S092577210900090X
| journal = Computational Geometry
| volume = 43 | issue = 2 | year = 2010 | pages = 73–83
| doi = 10.1016/j.comgeo.2009.04.003
}} and optimal triangulation in mesh generation with its element's size.{{cite journal
| last1 = Bern | first1 = Marshall
| last2 = Eppstein | first2 = David | author-link2 = David A. Eppstein
| title = Mesh Generation and Optimal Triangulation
| url = https://www.worldscientific.com/doi/abs/10.1142/9789812831699_0003
| doi = 10.1142/9789812831699_0003
| journal = Computing in Euclidean Geometry
| series = Lecture Notes Series on Computing
| pages = 47–123
| year = 1995
| volume = 4
| isbn = 978-981-02-1876-8
}}
References
{{reflist}}