Quadrilateral and tetrahedral mesh stripification using 2-factor partitioning of the dual graph

摘要

In order to find a 2-factor of a graph, there exists a O(n~(1.5)) deterministic algorithm and a O(n~3) randomized algorithm. In this paper, we propose novel O(n log~3 n log log n) algorithms to find a 2-factor, if one exists, of a graph in which all n vertices have degree 4 or less. Such graphs are actually dual graphs of quadrilateral and tetrahedral meshes. A 2-factor of such graphs implicitly defines a linear ordering of the mesh primitives in the form of strips. Further, by introducing a few additional primitives, we reduce the number of tetrahedral strips to represent the entire tetrahedral mesh and represent the entire quad surface using a single quad strip.