Donald Bren School of Information and Computer Sciences

We show that any simply connected (but not necessarily convex) polyhedron with an even number of quadilateral 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.