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|