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