^{1} Department of Mathematics, Technical University of Denmark^{2} Department of Applied Mathematics and Computer Science, Technical University of Denmark

Abstract:

A monotone path system (MPS) is a finite set of pairwise disjointpaths (polygonal arcs) in the plane such that every horizontal line intersectseach of the paths in at most one point. We consider a simple polygon in thexy-plane which bounds the simple polygonal (closed) region D. Let T and B betwo finite, disjoint, equicardinal sets of points of D. We give a min-maxrelation for the maximum number of points of T and B which can be joined bya MPS in D, and a polytime algorithm for finding such a MPS.