# David Eppstein - Publications

##

**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 (abstract
for video).

*25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics '04)*,
Grenoble, 2004 (2nd best paper award).

*Eurographics Forum* 23 (3): 371–379, 2004.

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.

(Graphics
lab pubs page)

Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.