论文标题
恒定因子近似，用于通过飞机中的连接障碍物导航
A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane
论文作者
论文摘要
给定平面中的两个S和T，以及由封闭曲线定义的一组障碍物，连接S和T的路径触摸的最小障碍物是多少？这是一个基本且研究充分的问题，在计算几何学，图形理论（以最小颜色路径和最小标签路径为单位），无线传感器网络（屏障弹性）和运动计划（最小约束去除）中自然产生。即使对于非常简单的障碍物，例如单位长线段，它仍然保持NP-HARD。在本文中，我们为此问题提供了第一个常数因子近似算法，解决了[Chan和Kirkpatrick，TCS，2014年]和[Bandyapadhyay等，CGTA，2020年]的开放问题。我们还获得了最低颜色奖品收集Steiner森林的恒定因子近似，目标是连接多个请求对（S1，T1），。 。 。 ，（SK，TK）虽然将任何（SI，TI）路径触摸的障碍物数量最小化，并为每对（SI，TI）固定的固定成本固定。这概括了经典的Steiner森林和平面图上的Steiner森林问题，为此，它是已知的复杂的Ptases。相比之下，即使在平面图上，也无法使用Min色路径的PTA，因为该问题已知是APXHARD [EIBEN和KANJ，TALG，2020年]。此外，我们表明问题概括了断开连接的障碍
Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory (under the names Min-Color Path and Minimum Label Path), wireless sensor networks (Barrier Resilience) and motion planning (Minimum Constraint Removal). It remains NP-hard even for very simple-shaped obstacles such as unit-length line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al., CGTA, 2020]. We also obtain a constant factor approximation for the Minimum Color Prize Collecting Steiner Forest where the goal is to connect multiple request pairs (s1, t1), . . . ,(sk, tk) while minimizing the number of obstacles touched by any (si, ti) path plus a fixed cost of wi for each pair (si, ti) left disconnected. This generalizes the classic Steiner Forest and Prize-Collecting Steiner Forest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for Min-Color Path even on planar graphs since the problem is known to be APXhard [Eiben and Kanj, TALG, 2020]. Additionally, we show that generalizations of the problem to disconnected obstacles
