Minimum cell connection in line segment arrangements

Article


Alt, H., Cabello, S., Giannopoulos, P. and Knauer, C. 2017. Minimum cell connection in line segment arrangements. International Journal of Computational Geometry and Applications. 27 (3), pp. 159-176. https://doi.org/10.1142/s0218195917500017
TypeArticle
TitleMinimum cell connection in line segment arrangements
AuthorsAlt, H., Cabello, S., Giannopoulos, P. and Knauer, C.
Abstract

We study the complexity of the following cell connection 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.
We show that problems (i) and (ii) are NP-hard and discuss some special, tractable cases. Most notably, we provide a near-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. 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.

Research GroupFoundations of Computing group
PublisherWorld Scientific Publishing Co. Pte Ltd
JournalInternational Journal of Computational Geometry and Applications
ISSN0218-1959
Electronic1793-6357
Publication dates
Print01 Sep 2017
Online31 Jan 2018
Publication process dates
Deposited15 May 2015
Submitted27 Dec 2012
Accepted25 Apr 2016
Output statusPublished
Accepted author manuscript
Copyright Statement

Publisher permits use of author's corrected copy.
Electronic version of an article published as Minimum Cell Connection in Line Segment Arrangements, Helmut Alt, Sergio Cabello, Panos Giannopoulos, and Christian Knauer,
International Journal of Computational Geometry & Applications 2017 27:03, 159-176, https://doi.org/10.1142/S0218195917500017 © [copyright World Scientific Publishing Company] http://www.worldscientific.com/worldscinet/ijcga

Digital Object Identifier (DOI)https://doi.org/10.1142/s0218195917500017
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/85555

Download files


Accepted author manuscript
  • 25
    total views
  • 14
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

Orthogonal terrain guarding is NP-complete
Bonnet, E. and Giannopoulos, P. 2018. Orthogonal terrain guarding is NP-complete. 34th International Symposium on Computational Geometry (SoCG 2018). Budapest, Hungary 11 - 14 Jun 2018 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. pp. 11:1-11:15 https://doi.org/10.4230/LIPIcs.SoCG.2018.11
Low-crossing spanning trees: an alternative proof and experiments
Giannopoulos, P., Konzack, M. and Mulzer, W. 2014. Low-crossing spanning trees: an alternative proof and experiments. European Workshop on Computational Geometry. Ein-Gedi, Israel 03 - 05 Mar 2014
QPTAS and subexponential algorithm for maximum clique on disk graphs
Bonnet, E., Giannopoulos, P., Kim, E., Rzążewski, P. and Sikora, F. 2018. QPTAS and subexponential algorithm for maximum clique on disk graphs. 34th International Symposium on Computational Geometry. Budapest, Hungary 11 - 14 Jun 2018 Dagstuhl, Germany Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. pp. 12:1-12:15 https://doi.org/10.4230/LIPIcs.SoCG.2018.12
On the parameterized complexity of red-blue points separation
Bonnet, E., Giannopoulos, P. and Lampis, M. 2018. On the parameterized complexity of red-blue points separation. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Vienna, Austria 06 - 08 Sep 2017 LIPICS Schloss Dagstuhl. pp. 8:1-8:13 https://doi.org/10.4230/LIPIcs.IPEC.2017.8
The complexity of separating points in the plane
Cabello, S. and Giannopoulos, P. 2016. The complexity of separating points in the plane. Algorithmica. 74 (2), pp. 643-663. https://doi.org/10.1007/s00453-014-9965-6