バリア形成：最小本数の線分で多角形集合を分離する
Barrier Forming: Separating Polygonal Sets with Minimum Number of Lines
平面上の複数の物体集合を最小本数の線分（バリア）で分離する問題を構造的・アルゴリズム的に研究し、点集合や障害物を含む設定での最適解法と近似解法を提案した。
著者: Si Wei Feng, Jingjin Yu
分類: cs.RO
原文アブストラクト
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.
