Nimrod Megiddo
Algorithmica
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.
Nimrod Megiddo
Algorithmica
Miklos Ajtai, Nimrod Megiddo
STOC 1992
Daphne Keller, Nimrod Megiddo, et al.
STOC 1994
Daniela Pucci De Farias, Nimrod Megiddo
Journal of the ACM