Advanced search
Start date

Heuristics for determining the flip distance between triangulations

Grant number: 15/09789-1
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): August 01, 2015
Effective date (End): December 31, 2016
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Pedro Jussieu de Rezende
Grantee:Yuri Corrêa Pinto Soares
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


This research project aims to study the problem of determining the inversion distance between triangulations. Given two triangles that share an edge in a triangulation and whose union forms a convex quadrilateral, an edge-inversion is the replacement of the edge shared by them by the other diagonal of the quadrilateral they form. Given two triangulation T1 and T2 of a set of points, it is known that a set of edge inversions can always be found that when applied to T1 produces T2. The problem of minimizing the number of inversions that allow us to obtain T2 from T1 is NP-hard, even when T1 and T2 are triangulations of a simple polygon. This number is the (edge) inversion distance between T1 and T2. The development of efficient heuristics able to obtain good viable solutions to this problem should lead to solutions of better quality than those obtained by approximation algorithms. In this study, we will apply the metaheuristics BRKGA and GRASP to the problem of obtaining good and efficient solutions for the inversion distance between triangulations and will carry out statistical tests for measuring the quality of solutions and their runtime. We intend to consider, in this context, triangulations of arbitrary sets of point as well as of simple and convex polygons, since in the latter case the complexity of the problem remains unknown.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items