Separating objects in the plane by wedges and strips

In this paper we study the separability of two disjoint sets of objects in the plane according to two criteria: wedge separability and strip separabil ity. We give algorithms for computing all the separating wedges and strips, the wedges with the maximum and minimum angle, and the narrowest and the w idest strip. The objects we consider are points, segments, polygons and cir cles. As applications, we improve the computation of all the largest circle s separating two sets of line segments by a log n factor, and we generalize the algorithm for computing the minimum polygonal separator of two sets of points to two sets of line segments with the same running time. (C) 2001 E lsevier Science B.V. All rights reserved.