Minimum cell connection and separation in line segment arrangements
  We study the complexity of the following cell connection and separation problems in segment arrangements. Given a set of straight-line segments in the plane and two points $a$ and $b$ in different cells of the induced arrangement:   (i) compute the minimum number of segments one needs to remove so that there is a path connecting $a$ to $b$ that does not intersect any of the remaining segments; (ii) compute the minimum number of segments one needs to remove so that the arrangement induced by the remaining segments has a single cell; (iii) compute the minimum number of segments one needs to retain so that any path connecting $a$ to $b$ intersects some of the retained segments.   We show that problems (i) and (ii) are NP-hard and discuss some special, tractable cases. Most notably, we provide a linear-time algorithm for a variant of problem (i) where the path connecting $a$ to $b$ must stay inside a given polygon $P$ with a constant number of holes, the segments are contained in $P$, and the endpoints of the segments are on the boundary of $P$. For problem (iii) we provide a cubic-time algorithm. 
Helmut Alt, Sergio Cabello, Panos Giannopoulos and Christian Knauer
cs.CG cs.DS