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 .[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.0 1.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.
- ↑ "Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm". SIAM Journal on Computing 13 (3): 488–507. 1984. doi:10.1137/0213031. https://epubs.siam.org/doi/abs/10.1137/0213031.
- ↑ 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. https://link.springer.com/article/10.1007/BF02187806.
- ↑ Erickson, Jeff (June 8–10, 2003). "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.
- ↑ 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. https://www.sciencedirect.com/science/article/pii/S092577210900090X.
- ↑ Bern, Marshall; Eppstein, David (1995). "Mesh Generation and Optimal Triangulation". Computing in Euclidean Geometry. Lecture Notes Series on Computing. 4. pp. 47–123. doi:10.1142/9789812831699_0003. ISBN 978-981-02-1876-8. https://www.worldscientific.com/doi/abs/10.1142/9789812831699_0003.
 |  |
