Removing Connected Obstacles in the Plane is FPT

2020/02/04 by Eiben, Eduard, Lokshtanov, Daniel
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2002.01218

Abstract

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 \textsfNP-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 (\textsfFPT) parameterized by k, by giving an algorithm with running time k^O(k3)n^O(1). Here n is the number connected areas in the plane drawing of all the obstacles.

Related

• How to navigate through obstacles?
• A Constant Factor Approximation for Navigating Through Connected\n Obstacles in the Plane
• Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
• Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles
• An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles