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
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Print)9781450320313
StatePublished - 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


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

Cite this