carrier image

An Experimental Comparison of Algorithms for Converting Triangulations of Closed Surfaces into Quadrangulations

Lemos, Thiago, Suneeta Ramaswami, Marcelo Siqueira

24th International Meshing Roundtable, Elsevier Ltd., pp.Research Note, October 12-14 2015


24th International Meshing Roundtable
Austin, TX
October 12-14,2014

Programa de Pos-Graduacao em Informatica, Universidade Federal do Parana, Curitiba, Brazil
Department of Computer Science, Rutgers University, Camden, NJ, USA
Departamento de Matematica, Universidade Federal do Rio Grande do Norte, Natal, Brazil

We perform an experimental comparison of four algorithms for converting a given triangulation T of an orientable, connected, boundaryless, and compact surface S in Ed into a quadrangulation Q of S. All algorithms compute Q by first pairing edge-adjacent triangles of T (of another triangulation of S with the same vertex set) so that every triangle belongs to exactly one pair. Such a perfect pairing is guaranteed for triangulations of boundaryless and compact surfaces (also known as closed surfaces). The common edge of each pair of matched triangles is then removed to give rise to a quadrilateral of Q. We implemented two greedy algorithms, a graph matching algorithm, and a new algorithm presented in this paper, which uses edge contractions and vertex splittings to compute a quadrangulation of the surface in two steps by combining pairings with edge flips. If T has positive genus g, the new algorithm takes O(gnf + g2) amortized time to compute a quadrangulation with the same vertex set, where nf is the number of triangles of the triangulation; otherwise (i.e., if the genus is zero), it takes O(nf) amortized time. We verify that if nf is large and g < < nf (which is typically the case in several applications), then our new algorithm performs better than the other three. However, if nf is not large enough or g is large (relative to nf), then a fast and simple greedy algorithm, when combined with an effective heuristic to pair up edge-adjacent triangles, is the best option among the four algorithms.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article