New results on stabbing segments with a polygon

We consider a natural variation of the concept of stabbing a set of segments with a simple polygon: a segment s   is stabbed by a simple polygon PP if at least one endpoint of s   is contained in PP, and a segment set S   is stabbed by PP if PP stabs every element of S. Given a segment set S  , we study the problem of finding a simple polygon PP stabbing S   in a way that some measure of PP (such as area or perimeter) is optimized. We show that if the elements of S are pairwise disjoint, the problem can be solved in polynomial time. In particular, this solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236–269 (2010)] [16] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. Our algorithm can also be extended to work for a more general problem, in which instead of segments, the set S consists of a collection of point sets with pairwise disjoint convex hulls. We also prove that for general segments our stabbing problem is NP-hard.