SCI graduate student Jason F. Shepherd and coauthor Carlos D. Carbonera have published a solution to Problem #27 of The Open Problems Project’s list of unresolved problems in computational geometry. The question is:

Can the interior of every simply connected polyhedron whose surface is meshed by an even number of quadrilaterals be partitioned into a hexahedral mesh compatible with the surface meshing?

The solution of Carbonera and Shepherd settles the practical aspects of the problem by demonstrating an explicit algorithm that extends a quadrilateral surface mesh to a hexahedral mesh where all the hexahedra have straight segment edges. This work did leave one aspect of the problem open. The authors did not resolve the question of achieving a hexahedral mesh with all planar faces. The collaborators are now working on a revision that should close this problem definitively.

C. D. Carbonera, J.F. Shepherd, “A Constructive Approach to Constrained Hexahedral Mesh Generation,” Proceedings, 15th International Meshing Roundtable, Birmingham, AL, September 2006.