Separating Bichromatic Point Sets by Fixed Angle Double Wedges

The point-set covering is one of the important problems in computational geometry, which has many applications. In this problem, the given points should be covered by at least one geometric shape. A variant of the problem is the point-set separation, in which there are at least two different kinds of points which are colored by different colors. The geometric shapes, which are called separators, should only cover the points of the same color. In this paper, separation of blue and red points by a double-wedge of a given angle θ is considered. The proposed algorithm reports all separator θ angle double-wedges in optimal time O(nlogn).