Separability by two lines and by nearly straight polygonal chains

AbstractIn this paper, we study the separability in the plane by two criteria: double-wedge separability and Θ-separability. We give an O(NlogN)-time optimal algorithm for computing all the vertices of separating double wedges of two disjoint sets of objects (points, segments, polygons and circles) and an O((N/Θ0)logN)-time algorithm for computing a nearly straight minimal Θ-polygonal chain separating two sets of points, where Θ0 is a value which depends on the position of the points