Computer Science – Computational Geometry
Scientific paper
2011-04-24
Computer Science
Computational Geometry
21 pages, 9 figures. About half of the results have appeared in the abstracts of EuroCG'11
Scientific paper
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.
Alt Helmut
Cabello Sergio
Giannopoulos Panos
Knauer Christian
No associations
LandOfFree
Minimum cell connection and separation in line segment arrangements does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Minimum cell connection and separation in line segment arrangements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum cell connection and separation in line segment arrangements will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-624010