Minimum Constraint Removal Problem for Line Segments is NP-hard
This resolves an open problem in computational geometry, showing that even simple line segment constraints make MCR NP-hard, which is incremental as it extends prior hardness results from arbitrary shapes to line segments.
The paper tackled the minimum constraint removal (MCR) problem for line segments, proving it is NP-hard for both weighted and unweighted cases using a reduction from the Subset Sum problem.
In the minimum constraint removal ($MCR$), there is no feasible path to move from the starting point towards the goal and, the minimum constraints should be removed in order to find a collision-free path. It has been proved that $MCR$ problem is $NP-hard$ when constraints have arbitrary shapes or even they are in shape of convex polygons. However, it has a simple linear solution when constraints are lines and the problem is open for other cases yet. In this paper, using a reduction from Subset Sum problem, in three steps, we show that the problem is NP-hard for both weighted and unweighted line segments.