A Min-max Relation for Monotone Path Systems in Simple Regions

Kathleen Cameron

    Research output: Book/ReportReportpeer-review

    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.
    Original languageEnglish
    Number of pages5
    Publication statusPublished - 1996

    Cite this