Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login