Transforming triangulations in polygonal domains (Q1315799)

Triangulations of a polygonal domain in the plane are the basic for many algorithms in the fields of finite element methods, scattered data interpolation, computational geometry etc. The efficiency of such algorithms frequently depends on the special triangulation. The authors prove that it is possible to transform every triangulation of a set of points inside a polygonal domain in the plane into every other triangulation of the same set of points using only operations of swapping diagonals in convex quadrilaterals. With the aid of this result it is possible to construct an algorithm to improve any initial triangulation with respect to a given criterion.