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

Kathleen Cameron

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

Kathleen Cameron

Research output: Book/Report › Report › Research › peer-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 language	English

Number of pages	5
Publication status	Published - 1996

OpenUrl availability

Full text

Cite this

@book{f98b55b847be400bbcd412cf9c6cc215,

title = "A Min-max Relation for Monotone Path Systems in Simple Regions",

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.",

author = "Kathleen Cameron",

year = "1996",

language = "English",

}

TY - RPRT

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

AU - Cameron, Kathleen

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

M3 - Report

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

ER -