%0 Journal Article
%T New results on stabbing segments with a polygon
%A Jos¨¦ Miguel D¨ªaz-B¨¢£¿ez
%A Matias Korman
%A Pablo P¨¦rez-Lantero
%A Alexander Pilz
%A Carlos Seara
%A Rodrigo I. Silveira
%J Computer Science
%D 2012
%I arXiv
%X We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon $\mathcal{P}$ if at least one of its two endpoints is contained in $\mathcal{P}$. A segment set $S$ is stabbed by $\mathcal{P}$ if every segment of $S$ is stabbed by $\mathcal{P}$. We show that if $S$ is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing $S$ can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by L\"offler and van Kreveld [Algorithmica 56(2), 236--269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments.
%U http://arxiv.org/abs/1211.1490v3