Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 21, 2021, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Nicolas Grelier
Given a set of points P, the minimum convex partition problem consists in partitioning the convex hull of P into convex polygons, such that no convex polygon contains a point in P in its interior, and the interiors of the convex polygons are pairwise disjoint. We consider the two variants whether we constrain the vertices of the polygons to be in P. In a previous talk, we showed that this problem is NP-hard, and that there exists an O(sqrt(n)log(n))-approximation algorithm. In this talk, we show the existence of an O(log(OPT))-approximation algorithm, where OPT denotes the minimum number of convex faces required.
Automatic MiSe System Software Version 1.4803M | admin login