Minimum cell connection and separation in line segment arrangements

Original · EN

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.