# ICS 269, Winter 1997: Theory Seminar

## 17 Jan 1997:

Flipping Edges in Triangulations

Jason Cahill, ICS, UC Irvine

This talk is based on a paper by F. Hurtado, M. Noy, and J.
Urrutia, from Computational Geometry '96. This paper covers three
problems, so I plan on covering two of them in detail, and showing
some examples of the other.
In this paper we study the problem of flipping edges in
triangulations of polygons and point sets. We prove that if a
polygon Qn has k reflex vertices, then any triangulation T of Qn
can be transformed to another triangulation T' of Qn by flipping at
most O(n + k^{2}) edges. We produce examples of
polygons with triangulations T and T' such that to transform T to
T' requires O(n^{2}) flips. These results are then extended
to triangulations of point sets. We also show that any
triangulation of an n point set contains at least
(n - 4) / 2 edges that can be flipped.