Single-strip triangulation of manifolds with arbitrary topology.
D. Eppstein and
M. Gopi.
13th Video Review of
Computational Geometry, 2004.
20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 455–456,
doi:10.1145/997817.997888
(abstract for video).
25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics '04),
Grenoble, 2004 (2nd best paper award).
Computer Graphics Forum 23 (3): 371–379, 2004,
doi:10.1111/j.1467-8659.2004.00768.x.
arXiv:cs.CG/0405036.
We describe a new algorithm, based on graph matching, for subdividing a triangle mesh (without boundary) so that it has a Hamiltonian cycle of triangles, and prove that this subdivision process increases the total number of triangles in the mesh by at most a factor of 3/2. We also prove lower bounds on the increase needed for meshes with and without boundary.