Minimum constraint removal problem for line segments is NP-hard

DOI10.1142/S1793830922500550MaRDI QIDQ6174134zbMATH OpenOpenAlexFDO

Authors Bahram Sadeghi Bigham

Publication date 14 July 2023

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.03140

zbMATH Keywords

algorithmcomputational geometryline segmentsMCRmotion planning

Mathematics Subject Classification ID

Numerical analysis (65-XX) Computer science (68-XX)

Abstract: 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.

Cites work

• Cayley graphs on nilpotent groups with cyclic commutator subgroup are Hamiltonian

This page was built for publication: Minimum constraint removal problem for line segments is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174134)