Stabbing Polygons by Monotone Chains

Abstract

Consider the problem of computing a stabber for polygonal objects. Given a set of objects $S$, an object that intersects with all of them is called the stabber of $S$. Polynomial time algorithms for constructing a line segment stabber for polygonal objects, if one exists, have been reported in the literature. We introduce the problem of stabbing polygonal objects by monotone chains. We show that a monotone chain that stabs the maximum number of given obstacles can be computed in $O(n^2\log n)$ time. We also prove that the maximum number of monotone chains required to stab all polygons can be computed in $O(n^{2.5})$ time. The main tool used in developing both results is the construction of a directed acyclic graph induced by polygonal objects in a given direction. These results have applications for planning collision-free disjoint paths for several mobile robots in a manufacturing environment.