Computing circular separability

Abstract

Two sets of planar points S1 and S2 are circularly separable if there is a circle that encloses S1 but excludes S2. We show that deciding whether two sets are circularly separable can be accomplished in O(n) time using linear programming. We also show that a smallest separating circle can be found in O(n) time, and largest separating circles can be found in O(n log n) time. Finally we establish that all these results are optimal. © 1986 Springer-Verlag New York Inc.