McGill University - School of Computer Science

# Algorithms Seminar

Everybody is welcome.

 DATE: Wednesday, October 6th, 1999 TIME: 16:30-17:30 PLACE: McConnell 320 TITLE: Triangulations On Surfaces. SPEAKER: Carmen Cortes, University of Sevilla. Department of Matematica Aplicada I

Given a triangulation T of a set of points (or a polygon) in the plane, and edge e of T is flippable if it is incident to two triangles whose union is a convex quadrilateral Q. By flipping e we mean the operation of removing e from T and replacing it by the other diagonal of Q. It is known that any two triangulations of a set of points (or a polygon) in the plane can be transformed into each other by a sequence of flips [1].

We generalize the operation of flipping an edge in a triangulation to other surfaces, such as the sphere, the cylinder and the torus. We prove that the result above holds for triangulations of point sets and for polygons on both the sphere and the cylinder and we point out the exceptional behaviour of the torus when we deal with this problem.

[1] C.L.Lawson. Software for surface interpolation. Mathematicas Software III, 161-194, Academic Press, 1977.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at cgm-help@cgm.cs.mcgill.ca.