Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 03.11.2011 at 12:20 in S6, there is the following noon lecture:

Non-crossing Connectors in the Plane

Torsten Ueckerdt

Technische Universitšt Berlin

Abstract

Consider a set of simply connected regions R1,...,Rn in the plane, where additionally every region Ri contains a set Pi - think of Pi as a finite point set. We ask whether there are pairwise disjoint and connected sets C1,...,Cn such that Pi is contained in Ci which in turn is contained in Ri. Such sets are called non-crossing connectors.

We prove that if every Pi is finite and the Ri are pseudo-disks, then non-crossing connectors always exist. However, if a pair of regions is allowed to have 4 common boundary points, the decision problem becomes NP-hard, even if |Pi| = 2.

We also consider special cases and variants of the problem, where one distinguished point in Pi has to be connected to any of the other points.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010