Barrier Forming: Separating Polygonal Sets with Minimum Number of Lines
Si Wei Feng,Jingjin Yu,Si Wei Feng,Jingjin Yu
In this work, we carry out structural and al-gorithmic studies of a problem of barrier forming: selecting the minimum 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 ...
