Return to Colloquia & Seminar listing
The minimum-weight triangulation problem
Algebra & Discrete Mathematics| Speaker: | David Haws, UC Davis |
| Location: | 1147 MSB |
| Start time: | Thu, May 4 2006, 12:10PM |
Description
The minimum-weight triangulation problem is the problem of finding a triangulation, for an input
planar point set, which minimizes
the sum of Euclidean lengths on the edges present.
In the first part of this talk we survey the very
recent breakthrough, by Mulzer and Rote, asserting that the problem is actually NP-hard.
Due to this, it is of interest to find practical way
of finding a minimal triangulation in given instances. In the second part of talk we outline a
novel approach via integer and linear programming.
We conclude the talk with a report on experimental
results.
This is joint work with J. De Loera