INTRODUCTION

Then given two triangulations an important question arises as to can one triangulation be obtained from another in a series of edge flip operations?  The question as to if one triangulation can be obtained from a given triangulation of points is of considerable interest in such areas as computational geometry, optimization, geometric combinatorics as well as many others...  

Edge flipping, being a natural and simple transformation of a triangulation, is applicable to many areas of computational geometry.  Mesh generation, Delaunay triangulation and many other areas have used the concept of edge flipping.

To begin we will give some definitions...

Given a triangulation T of a set P of points on the plane, a edge e of T is flippable if it is adjacent to two triangles whose union is a convex quadrilateral C.  By flipping e we mean the operation of removing e from T and replacing it by the other diagonal of C. 

By this method we obtain a new triangulation T' of P, and we say that T' has been obtained from T by means of a flip.