
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 1214 2015

IMR PROCEEDINGS

24th International Meshing Roundtable
Austin, TX
October 1214,2014
Programa de PosGraduacao 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
Email: suneeta.ramaswami@rutgers.edu
Abstract
We perform an experimental comparison of four algorithms for converting a given triangulation T of an orientable, connected,
boundaryless, and compact surface S in E^{d} into a quadrangulation Q of S. All algorithms compute Q by first pairing edgeadjacent
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(gn_{f} + g^{2}) amortized time to compute a quadrangulation with the same vertex set, where n_{f} is the number of
triangles of the triangulation; otherwise (i.e., if the genus is zero), it takes O(n_{f}) amortized time. We verify that if n_{f} is large and
g < < n_{f} (which is typically the case in several applications), then our new algorithm performs better than the other three. However,
if n_{f} is not large enough or g is large (relative to n_{f}), then a fast and simple greedy algorithm, when combined with an effective
heuristic to pair up edgeadjacent 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
