Removing Connected Obstacles in the Plane is FPT

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 $\text{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 ($\text{FPT}$) parameterized by $k$, by giving an algorithm with running time $k^{O(k^3)}{n}^{O(1)}$. Here $n$ is the number connected areas in the plane drawing of all the obstacles.