McGill University - School of Computer Science

Algorithms Seminar Winter 2001

Everybody is welcome!

DATE: Friday, May 11th
TIME: 3:00 PM - 4:00 PM
PLACE: McConnell 320
TITLE: Enumerating triangulations of convex polytopes in R^3
SPEAKER: Sergei Bespamyatnikh, Department of Computer Science, University of British Columbia

A triangulation of a finite point set A in R^d is a geometric simplicial complex which covers the convex hull of A and whose vertices are points of A. We study the graph of triangulations whose vertices represent the triangulations and whose edges represent geometric bistellar flips. The main result is that the graph of triangulations in three dimensions is connected when points of A are in convex position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in O(loglogn) time per triangulation.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.