Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 14, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Nicolas Grelier
We consider the Minimum Convex Partition problem: Given a set P of n points in the plane, draw a plane a graph G on P, with positive minimum degree, such that G partitions the convex hull of P into a minimum number of convex faces. We show that Minimum Convex Partition is NP-hard, and we give a O(sqrt(n) log(n))-approximation algorithm running in quadratic time. The latter result is obtained by relating the problem to another geometric problem: Given a set of points P, cover P with a minimum number of lines.
A constant-factor approximation algorithm was shown for Minimum Convex Partition by Knauer and Spillner, for point sets where no three points are on a line (SWAT 2006). This restriction is crucial for the algorithm to work. The complexity of the problem under this restriction remains open.
Automatic MiSe System Software Version 1.4803M | admin login