A min-max relation for monotone path systems in simple regions (Q5928596)

A monotone path system (MPS) is a finite set of pairwise disjoint paths in the plane such that every horizontal line intersects each of the paths in at most one point. Let \(T\) and \(B\) be two finite, disjoint, equicardinal sets of points in a simple closed polygonal region \(D\). In this paper a min-max relation for the maximum number of points of \(T\) and \(B\) which can be joined by MPS is given. A polytime algorithm for finding such an MPS is also presented.