| 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.