A fast algorithm for computing irreducible triangulations of closed surfaces in $E^d$

Abstract

We give a fast algorithm for computing an irreducible triangulation $T^{\prime }$ of an oriented, connected, boundaryless, and compact surface $S$ in $E^d$ from any given triangulation $T$ of $S$. If the genus $g$ of $S$ is positive, then our algorithm takes $O(g^2+gn)$ time to obtain $T^{\prime }$, where $n$ is the number of triangles of $T$. Otherwise, $T^{\prime }$ is obtained in linear time in $n$. While the latter upper bound is optimal, the former upper bound improves upon the currently best known upper bound by a $(\lg n/g)$ factor. In both cases, the memory space required by our algorithm is in $\Theta (n)$.

52 pages, a shorter version of this Technical Report is about to be submitted to Elsevier Journal Computational Geometry: Theory and Applications

References in corpus (3)

• Irreducible triangulations of low genus surfaces
• Generating irreducible triangulations of surfaces
• Irreducible triangulations of surfaces with boundary