论文标题
消除飞机上的连接障碍物是fpt
Removing Connected Obstacles in the Plane is FPT
论文作者
论文摘要
鉴于飞机上的两个点，一组由封闭曲线定义的障碍物和一个整数$ k $，是否有两个指定点之间有一条路径，最多与障碍物的$ k $相交？这是一个基本且研究充分的问题，在计算几何，图理论，无线计算和运动计划中自然产生。它仍然是$ \ textsf {np} $ - 即使障碍物是非常简单的几何形状（例如，单位长度线段）也很难。在本文中，我们表明该问题是固定参数可处理的（$ \ textsf {fpt} $）由$ k $参数化的，该算法在运行时间$ k^{o（k^3）} n^{o（o（k^3）} n^{o（1）} $中。这里$ n $是所有障碍的飞机图中连接的区域。
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 $\textsf{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 ($\textsf{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.
