Removing Connected Obstacles in the Plane Is FPT
Lists
Only you see this
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
@inproceedings{eiben2020removing,
author = {Eduard Eiben and Daniel Lokshtanov},
title = {{Removing Connected Obstacles in the Plane Is FPT}},
booktitle = {SoCG},
year = {2020},
doi = {10.4230/lipics.socg.2020.39},
}Loading related content...