# Noon lecture

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

On 3.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 R_{1},...,R_{n} in the plane, where additionally every region R_{i} contains a set P_{i} - think of P_{i} as a finite point set. We ask whether there are pairwise disjoint and connected sets C_{1},...,C_{n} such that P_{i} is contained in C_{i} which in turn is contained in R_{i}. Such sets are called non-crossing connectors.

We prove that if every P_{i} is finite and the R_{i} 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 |P_{i}| = 2.

We also consider special cases and variants of the problem, where one distinguished point in P_{i} 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 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page