BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We study the following separation problem: Given a collection
of colored objects in the plane\, compute a shortest "fence" F\, i.e.\, a u
nion of curves of minimum total length\, that separates every two objects o
f different colors. Two objects are separated if F contains a simple closed
curve that has one object in the interior and the other in the exterior. W
e refer to the problem as GEOMETRIC k-CUT\, where k is the number of differ
ent colors\, as it can be seen as a geometric analogue to the well-studied
multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm
that computes an optimal fence for the case where the input consists of pol
ygons of two colors and n corners in total. We then show that the problem i
s NP-hard for the case of three colors. Finally\, we give a 4/3*1.2965-appr
oximation algorithm. Joint work with Panos Giannopoulos\, Maarten Löffler
\, and Günter Rote. Presented at ICALP 2019.
DTSTAMP:20200330T142000
DTSTART:20200427T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Mikkel Abrahamsen (University of Copenhagen): Geometric Multicut: S
hortest Fences for Separating Groups of Objects in the Plane - cancelled
UID:105463982@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200427-L-Abrahamsen.html
END:VEVENT
END:VCALENDAR