Department of
Applied
Mathematics

Non-crossing Connectors in the Plane

Torsten Ueckerdt

Technische Universität Berlin

Abstract

Consider a set of simply connected regions R₁,...,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₁,...,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.