Efficiently hex-meshing things with topology

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A topological quadrilateral mesh Q of a connected surface in ℝ3 can be extended to a topological hexahedral mesh of the interior domain Ω if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds 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 respects Q. Finally, if Q is given as a polyhedron in ℝ3 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)
Title of host publicationProceedings of the 29th Annual Symposium on Computational Geometry, SoCG 2013
Number of pages9
StatePublished - Jul 8 2013
Event29th Annual Symposium on Computational Geometry, SoCG 2013 - Rio de Janeiro, Brazil
Duration: Jun 17 2013Jun 20 2013

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Other29th Annual Symposium on Computational Geometry, SoCG 2013
CityRio de Janeiro


  • Computational topology
  • Hexahedral mesh generation
  • Homology

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Efficiently hex-meshing things with topology'. Together they form a unique fingerprint.

Cite this