Optimal Algorithms for Stabbing Polygons by Monotone Chains and Paths

Two algorithms to compute monotone stabbers for convex polygons are presented. More precisely, given a set of \(m\) convex polygons with \(n\) vertices in total, we want to stab the polygons with an $z$-monotone polygonal chain such that each polygon is entered at its leftmost point and exited at its rightmost point. Since such a stabber does not exist in general, we study two related problems. The first problem requests a monotone stabber that stabs as many convex polygons as possible. The second problem is to compute the minimal number of \(x\)-monotone stabbers that are necessary to stab all given convex polygons. We present optimal \(O(m \log m + n)\) algorithms for both problems.