License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.39
URN: urn:nbn:de:0030-drops-121972
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12197/
Go to the corresponding LIPIcs Volume Portal

Eiben, Eduard ; Lokshtanov, Daniel

Removing Connected Obstacles in the Plane Is FPT

pdf-format:
LIPIcs-SoCG-2020-39.pdf (0.9 MB)

Abstract

Given two points in the plane, a set of obstacles defined by closed curves, and an integer k, does there exist a path between the two designated points intersecting at most k of the obstacles? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory, wireless computing, and motion planning. It remains NP-hard even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). In this paper, we show that the problem is fixed-parameter tractable (FPT) parameterized by k, by giving an algorithm with running time k^O(k³) n^O(1). Here n is the number connected areas in the plane drawing of all the obstacles.

BibTeX - Entry

@InProceedings{eiben_et_al:LIPIcs:2020:12197,
  author =	{Eduard Eiben and Daniel Lokshtanov},
  title =	{{Removing Connected Obstacles in the Plane Is FPT}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12197},
  URN =		{urn:nbn:de:0030-drops-121972},
  doi =		{10.4230/LIPIcs.SoCG.2020.39},
  annote =	{Keywords: parameterized complexity and algorithms, planar graphs, motion planning, barrier coverage, barrier resilience, colored path, minimum constraint removal}
}

Keywords: parameterized complexity and algorithms, planar graphs, motion planning, barrier coverage, barrier resilience, colored path, minimum constraint removal
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI