Discrete & Computational Geometry 52(3):427–449, 2014

(special issue of invited papers from
the 29th Annual Symposium on Computational Geometry)

Proceedings of the 29th Annual Symposium on Computational Geometry, 37–46, 2013.

- Download journal version (final except for copy-editing):
- Download SOCG version:
- Download slides (long version):

Abstract:

A topological quadrilateral meshQof a connected surface inR³ can be extended to a topological hexahedral mesh of the interior domain Ω if and only ifQhas an even number of quadrilaterals and no odd cycle inQbounds a surface inside Ω. Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of Ω that respectsQ. Finally, ifQis given as a polyhedron inR³ with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 09 Oct 2014