Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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