2026-07-26T04:50:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12197 2024-03-06T10:49:41Z ddc:004 open_access

Removing Connected Obstacles in the Plane Is FPT Eiben, Eduard Lokshtanov, Daniel parameterized complexity and algorithms planar graphs motion planning barrier coverage barrier resilience colored path minimum constraint removal 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and Daniel Lokshtanov 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.39 urn:nbn:de:0030-drops-121972 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.39 eng https://creativecommons.org/licenses/by/3.0/legalcode