Computing circular separability (Q1079817)

Let \(S_ 1\) and \(S_ 2\) be two sets of points in \(R^ 2\) with \(| S_ 1| +| S_ 2| =n\). \(S_ 1\) and \(S_ 2\) are said to be circularly separable if there is a circle C such that each point of \(S_ 1\) is interior to or on the boundary of C while each point of \(S_ 2\) is exterior to or on the boundary of C. The results of this paper consist of: 1) deciding whether two sets \(S_ 1\) and \(S_ 2\) are circularly separable and showing that this decision can be achieved with the speed O(n); 2) finding a smallest separating circle and showing that it can be found in O(n) time; 3) finding all largest separating circles and showing that this can be accomplished in O(n log n) time. It is also proved that these results are optimal. These problems can be extended to spherical separability in higher dimensions. The authors derive the corresponding results.