Treffer: A fast algorithm for computing irreducible triangulations of closed surfaces in Ed: A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\)
http://arxiv.org/abs/1409.6015
https://zbmath.org/6840495
https://doi.org/10.1016/j.comgeo.2017.05.007
https://dblp.uni-trier.de/db/journals/corr/corr1409.html#RamaswamiS14
https://www.sciencedirect.com/science/article/pii/S0925772117300408
https://www.researchwithrutgers.com/en/publications/a-fast-algorithm-for-computing-irreducible-triangulations-of-clos
https://ui.adsabs.harvard.edu/abs/2014arXiv1409.6015R/abstract
https://www.researchwithnj.com/en/publications/a-fast-algorithm-for-computing-irreducible-triangulations-of-clos
arXiv Non-Exclusive Distribution
Weitere Informationen
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 $Θ(n)$.
52 pages, a shorter version of this Technical Report is about to be submitted to Elsevier Journal Computational Geometry: Theory and Applications