Efficiently Hex-Meshing Things with Topology

Research output: Contribution to journalArticlepeer-review


A topological quadrilateral mesh Q of a connected surface in (Formula Prseented.) can be extended to a topological hexahedral mesh of the interior domain (Formula Prseented.) if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds a surface inside (Formula Prseented.). 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 (Formula Prseented.) that respects Q. Finally, if Q is given as a polyhedron in (Formula Prseented.) 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.

Original languageEnglish (US)
Pages (from-to)427-449
Number of pages23
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - Sep 1 2014


  • Computational topology
  • Cube complexes
  • Homology
  • Mesh generation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Efficiently Hex-Meshing Things with Topology'. Together they form a unique fingerprint.

Cite this