  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.
