Monotone path systems in simple regions (Q1323475)

A hexagonal system \(H\) is a finite connected plane graph with no cut nodes in which every interior face is bounded by a unit hexagon. If \(H\) is drawn such that some edges are vertical one can define monotone paths, which intersect every horizontal line at most once, and perfect path systems, which are systems of disjoint monotone paths that connect the locally highest points (peaks) with the locally lowest points (valleys). A perfect path system produces a pairing of the peaks with the valleys. How does the pairing depend on the perfect path system? In order to answer that question (``Not at all'') the authors widen the scope and define a monotone path system (MPS) to be a finite set of pairwise disjoint paths in the plane such that every horizontal line intersects each of the paths in at most one point. An MPS naturally determines a pairing of its top points with its bottom points. Let \(\Delta\) be a simple polygon which bounds the (closed) polygonal region \(D\), and let \(T\) and \(B\) two finite, disjoint sets of equally many points of \(D\). The authors give a good characterization for the existence of an MPS in \(D\) which pairs \(T\) and \(B\), and a good algorithm for finding such an MPS. They also solve the problem of finding all MPSs in MDM which pair \(T\) with \(B\), and give sufficient conditions for any such pairings to be the same. The notions used in the investigation are rather delicate, and the proofs are rather tedious.