Linear complexity hexahedral mesh generation.
D. Eppstein.
Tech. Rep. 95-51, ICS, UCI, 1995.
12th ACM Symp. Comp. Geom., Philadelphia,
1996, pp. 58–67,
doi:10.1145/237218.237237.
arXiv:cs.CG/9809109.
Comp. Geom. Theory & Applications 12: 3–16, 1999,
doi:10.1016/S0925-7721(98)00032-7
(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.