Alt, H., Cabello, S., Giannopoulos, P. ORCID: 0000000262611961 and Knauer, C. (2018). Minimum Cell Connection in Line Segment Arrangements. International Journal of Computational Geometry & Applications, 27(03), pp. 159176. doi: 10.1142/s0218195917500017
Abstract
We study the complexity of the following cell connection problems in segment arrangements. Given a set of straightline 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.
We show that problems (i) and (ii) are NPhard and discuss some special, tractable cases. Most notably, we provide a nearlineartime 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. The approach for this latter result uses homotopy of paths to group the segments into clusters with the property that either all segments in a cluster or none participate in an optimal solution.
Publication Type:  Article 

Additional Information:  Electronic version of an article published as Alt, H., Cabello, S., Giannopoulos, P. and Knauer, C. (2018). Minimum Cell Connection in Line Segment Arrangements. International Journal of Computational Geometry & Applications, 27(03) DOI: 10.1142/S0218195917500017] © copyright World Scientific Publishing Company https://www.worldscientific.com/worldscinet/ijcga 
Publisher Keywords:  Cell connection, segment arrangement, path homotopy 
Subjects:  Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science 
Departments:  School of Mathematics, Computer Science & Engineering > Computer Science 
URI:  http://openaccess.city.ac.uk/id/eprint/21510 

Text
 Accepted Version
Download (389kB)  Preview 
Export
Downloads
Downloads per month over past year
Actions (login required)
Admin Login 