Pseudotriangulations

A pseudotriangulation is a subdivision of the plane into so called pseudotriangles, similar to how a triangulation is a subdivision of the plane into triangles. A polygonal pseudotriangle is a simple polygon with exactly three corners, where a corner is a vertex of the polygon where the angle between its two incident edges on the interior of the polygon is less than π and non-corners being a vertex where the interior angles is greater than π.

Pseudotriangulations are a relatively new concept being introduced in its current form in 1993 by Pocchiola and Vegter's "The Visibility Complex", they are used in such fields as rigidity theory, collision detection, dynamic graph drawing and shape morphing. A pseudotriangulation can be transformed into another pseudotriangulation on the same point set by flipping edges. Every internal edge can be flipped to a unique other edge such that the resulting planar decomposition is also a pseudotriangulation.

By a series of such edge flips one pseudotriangulation can be transformed into a completely different pseudotriangulation. The minimum number of edge flips required to flip two given pseudotriangulations into one another is defined as the flip distance between these two pseudotriangulations. It has been proved that any two pseudotriangulations on the same point set have a flip distance asymptotically bounded by O(n log n), where n is the cardinality of the point set [Bereg 04].

The flip distance is also defined for triangulations, where the asymptotic bound is O(n2). There is however also an input sensitive bound which gives us that the number of flips is at most the number of interior intersections between the edges in the union of the two triangulations [Hanke 96]. My thesis project was to examine the possibility of a similar input sensitive bound for pseudotriangulations. A more detailed description of the problem and the results of my research can be found in my thesis, "On the Flip Distance of Pointed Pseudotriangulations."