|
|
Flipping Edged in Triangulations |
|
APPLICATIONSAreas involved in edge flipping? 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. It is an exciting area in that it combines research from a number of different areas in computer science. More specially, research has been done on using edge flipping and combinatorial games on triangulations to investigate the properties of triangulations of point sets. Specific algorithms using edge flipping are reduced to known combinatorial games, which thus, reveal such properties. Optimal Triangulations Edge flipping has been used in algorithms for finding triangulations that are optimum in terms of the maximum angle, maximum vertex degree, total edge length and many more. Edge flipping then gives a very simplistic algorithm to find triangulations of such properties; begin with any initial triangulation and flip respective edges until the desired triangulation is achieved. Delaunay Triangulations The first reason is the existence of a simple greedy algorithm that constructs the Delaunay triangulation of a point set in general position by successive flips starting from an arbitrary triangulation of the point set. In this algorithm the iteration of local improvements produces a global optimum. This greedy algorithm is applied in many commercial applications due to it's simplicity in coding. Triangulation Games Edge flipping is at the heart of most combinatorial games on triangulations. These triangulation games transform a current triangulation into a triangulation having a desired property and thus, reveal optimal or near-optimal algorithms to solve problems which are otherwise difficult. Many of the theorems investigated on this web-site have equivalent theorems in terms of combinatorial games. |
|
|
Last Updated
December 2, 2003 |
