Barrier Forming: Separating Polygonal Sets with Minimum Number of Lines
This addresses the challenge of efficiently isolating regions for practical security purposes, though it is incremental as it builds on known NP-hard separation problems.
The paper tackles the problem of separating disjoint polygonal sets in the plane using the minimum number of straight line segments, modeling applications like sensor placement for intrusion detection, and provides optimal solutions for point sets and point sets with obstacles, along with a 2-OPT approximation for polygonal sets with obstacles.
In this work, we carry out structural and algorithmic studies of a problem of barrier forming: selecting theminimum number of straight line segments (barriers) that separate several sets of mutually disjoint objects in the plane. The problem models the optimal placement of line sensors (e.g., infrared laser beams) for isolating many types of regions in a pair-wise manner for practical purposes (e.g., guarding against intrusions). The problem is NP-hard even if we want to find the minimum number of lines to separate two sets of points in the plane. Under the umbrella problem of barrier forming with minimum number of line segments, three settings are examined: barrier forming for point sets, point sets with polygonal obstacles, polygonal sets with polygonal obstacles. We describe methods for computing the optimal solution for the first two settings with the assistance of mathematical programming, and provide a 2-OPT solution for the third. We demonstrate the effectiveness of our methods through extensive simulations.