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(il) topological cubes, mee ting 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 generat ion problem to a finite case analysis amenable to machine solution. (C) 199 9 Elsevier Science B.V. All rights reserved.