Efficiently hex-meshing things with topology
type: Item
instance of: scholarly article
title: Efficiently hex-meshing things with topology
zbMATH Open document ID: 1311.57032
author: Jeff Erickson
published in: Discrete \& Computational Geometry
publication date: 2014-11-14T00:00:00Z
review text: This paper provides a complete solution to the topological hex-meshing problem, generalizing the results for manifolds of genus zero and bipartite meshes of \textit{W. P. Thurston}, ``Hexahedral decomposition of polyhedra'', Posting to Sci. Math. (1993). {\texttt{http://www.ics.uci.edu/~eppstein/gina/Thurston-hexahedra.html}}], \textit{S. A. Mitchell} [A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume. In: Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1046, 456--476. Springer, Berlin (1996)], and \textit{D. Eppstein} [Comput. Geom. 12, No. 1--2, 3--16 (1999; Zbl 0922.68120)]. In this setting, the input quadrilaterals and output hexahedra are not necessarily convex polygons or polyhedra, but rather topological disks and balls satisfying natural conditions on the intersections pattern. The main result of the paper is the following: Consider a compact connected domain \(\Omega\subset\mathbb{R}^3\) whose boundary \(\partial\Omega\) is a (possibly disconnected) 2-dimensional manifold. Let \(Q\) be a topological quadrilateral mesh of \(\partial\Omega\) with an even number of facets. Moreover, assume that in the case \(Q\) has more than one connected component, each of them consists of an even number of facets. Then the following statements are equivalent: (1) There exists a topological hexahedral mesh of \(\Omega\) whose boundary is \(Q\); (2) Every subgraph of \(Q\) that is the boundary of a (possibly self-intersecting) surface inside \(\Omega\) has an even number of edges; (3) The dual graph \(Q^*\) of \(Q\) is the boundary of an immersed surface in \(\Omega\). The equivalence (2)\(\Leftrightarrow\)(3) is proved in Lemma 1 using homological arguments; (1)\(\Rightarrow\)(3) follows from the properties of the dual of a hexahedral mesh; (3)\(\Rightarrow\)(1) is proved in two different ways that cover, respectively, Section…
reviewed by: Barbara Di Fabio
Mathematics Subject Classification ID: 57Q05
Mathematics Subject Classification ID: 65N50
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 57M99
zbMATH DE Number: 6369424
zbMATH Keywords: computational topology
zbMATH Keywords: mesh generation
zbMATH Keywords: cube complexes
zbMATH Keywords: homology
describes a project that uses: MathOverflow
describes a project that uses: ReebHanTun
MaRDI profile type: Publication
full work available at URL: s00454-014-9624-3
OpenAlex ID: W2089188765
cites work: Q3973296
cites work: Immersed surfaces in cubed manifolds
cites work: Counting faces of cubical spheres modulo two
cites work: Triple Points and Surgery of Immersed Surfaces
cites work: Q5617548
cites work: The theory of graphs. Translated from the 1958 French edition by Alison Doig.
cites work: Fiber polytopes
cites work: Locally tame sets are tame
cites work: An alternative proof that 3-manifolds can be triangulated
cites work: Triangular Factorization and Inversion by Fast Matrix Multiplication
cites work: Extending immersions of curves to properly immersed surfaces
cites work: Extending immersed circles in the sphere to immersed disks in the ball
cites work: Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
cites work: Triangulating a nonconvex polytope
cites work: Bounds on the size of tetrahedralizations
cites work: On the number of triple points of an immersed surface with boundary
cites work: An efficient computation of handle and tunnel loops via Reeb graphs
cites work: Q3655278
cites work: Linear complexity hexahedral mesh generation
cites work: Efficiently hex-meshing things with topology
cites work: Reliable whisker weaving via curve contraction
cites work: Titus' Homotopies of Normal Curves
cites work: Cubulations, immersions, mappability and a problem of habegger
cites work: Q4263284
cites work: Surface cubications mod flips
cites work: Immersions of surfaces in 3-manifolds
cites work: Q4819371
cites work: A generalization of the fast LUP matrix decomposition algorithm and applications
cites work: The lower and upper bound problems for cubical polytopes
cites work: The volume of hyperbolic alternating link complements
cites work: A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume
cites work: The all-hex geode-template for conforming a diced tretrahedral mesh to any diced hexahedral mesh
cites work: Affine structures in 3-manifolds. V: The triangulation theorem and Hauptvermutung
cites work: Affine structures in 3-manifolds. VIII. Invariance of the knottypes; local tame imbedding
cites work: Hexahedral mesh generation by successive dual cycle elimination
cites work: Shelling hexahedral complexes for mesh generation
cites work: Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation
cites work: The spatial twist continuum: A connectivity based method for representing all-hexahedral finite element meshes
cites work: Diagonal transformations and cycle parities of quadrangulations on surfaces
cites work: Q4875682
cites work: Diagonal transformations in quadrangulations and Dehn twists preserving cycle parities
cites work: Complexity of plane and spherical curves
cites work: On Dehn's lemma and the asphericity of knots
cites work: Volumes of highly twisted knots and links
cites work: Q4938475
cites work: Q3116349
cites work: Construction Techniques for Cubical Complexes, Odd Cubical 4-Polytopes, and Prescribed Dual Manifolds
cites work: Q3222788
cites work: A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
cites work: The singularities of a smooth \(n\)-manifold in \((2n-1)\)-space
DOI: 10.1007/S00454-014-9624-3
description: scientific article; zbMATH DE number 6369424