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.

Number of pages | 5 |
---|

Publication status | Published - 1996 |
---|