Improved Results for Minimum Constraint Removal
Improved Results for Minimum Constraint Removal
复制标题
最小约束移除的改进结果
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
A. Youngdahl
中科院分区：
文献类型：
--
作者：
E. Eiben;Jonathan F. Gemmell;Iyad A. Kanj;A. Youngdahl
给定一组障碍物和平面上的两个指定点，最小约束移除问题要求可以移除的障碍物的最小数量，使得两个指定点之间存在无碰撞路径。这是一个在机器人运动规划和无线计算中得到充分研究的问题，在各种设置中已被证明是NP难的。在这项工作中，我们扩展了最小约束去除的研究。首先，我们提出了两种情况下的细化NP-硬度减少：（1）当所有的障碍物是轴平行的矩形，（2）当所有的障碍物是线段，没有三个相交于同一点。这些结果改进了文献中已有的结果。作为我们NP-困难减少的副产品，我们证明了，除非指数时间假设（ETH）失败，最小约束去除不能在次指数时间2 o（n）内解决，其中n是实例中障碍物的数量。这表明，暴力2 O（n）时间算法的显着改进是不可能的。然后，我们提出了一个次指数时间算法的最小约束删除的情况下，在任何一点重叠的障碍物的数量是恒定的，该算法运行在时间2 O（N），其中N是与问题的实例相关联的辅助图中的顶点数。我们表明，该算法的显着改进是不可能的，除非ETH失败，最小约束删除有界重叠数不能在时间2 o（N）解决。我们描述了几个精确的算法和近似算法，利用prostitics和讨论他们的表现在一个广泛的经验模拟。
Given a set of obstacles and two designated points in the plane, the Minimum Constraint Removal problem asks for a minimum number of obstacles that can be removed so that a collision-free path exists between the two designated points. It is a well-studied problem in both robotic motion planning and wireless computing that has been shown to be NP-hard in various settings. In this work, we extend the study of Minimum Constraint Removal. We start by presenting refined NP-hardness reductions for the two cases: (1) when all the obstacles are axes-parallel rectangles, and (2) when all the obstacles are line segments such that no three intersect at the same point. These results improve on existing results in the literature. As a byproduct of our NP-hardness reductions, we prove that, unless the Exponential-Time Hypothesis (ETH) fails, Minimum Constraint Removal cannot be solved in subexponential time 2o(n), where n is the number of obstacles in the instance. This shows that significant improvement on the brute-force 2O(n)-time algorithm is unlikely. We then present a subexponential-time algorithm for instances of Minimum Constraint Removal in which the number of obstacles that overlap at any point is constant; the algorithm runs in time 2O(√N), where N is the number of the vertices in the auxiliary graph associated with the instance of the problem. We show that significant improvement on this algorithm is unlikely by showing that, unless ETH fails, Minimum Constraint Removal with bounded overlap number cannot be solved in time 2o(√N). We describe several exact algorithms and approximation algorithms that leverage heuristics and discuss their performance in an extensive empirical simulation.