Linear Complexity Hexahedral Mesh Generation
<|reference_start|>Linear Complexity Hexahedral Mesh Generation: We show that any polyhedron forming a topological ball with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face. The result generalizes to non-simply-connected polyhedra satisfying an additional bipartiteness condition. The same techniques can also be used to reduce the geometric version of the hexahedral mesh generation problem to a finite case analysis amenable to machine solution.<|reference_end|>
@article{eppstein1998linear,
    title={Linear Complexity Hexahedral Mesh Generation},
    author={David Eppstein},
    journal={Comp. Geom. Theory & Appl. 12 (1999) 3-16},
    year={1998},
    doi={10.1016/S0925-7721(98)00032-7},
    archivePrefix={arXiv},
    eprint={cs/9809109},
    primaryClass={cs.CG}
}