ICS Theory Group

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 + k2) edges. We produce examples of polygons with triangulations T and T' such that to transform T to T' requires O(n2) 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.