Linear complexity hexahedral mesh generation.
D. Eppstein.
Tech. Rep. 95-51, ICS, UCI, 1995.
12th ACM Symp. Comp. Geom., Philadelphia,
1996, pp. 58–67.
arXiv:cs.CG/9809109.
Comp. Geom. Theory & Applications 12: 3–16, 1999
(special issue for 12th SCG).
Any simply connected polyhedron with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face.