Nimrod Megiddo
Journal of Algorithms
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
Journal of Algorithms
Nimrod Megiddo, Dharmendra S. Modha
FAST 2003
Nimrod Megiddo
Mathematical Programming
Noga Alon, Nimrod Megiddo
Journal of the ACM (JACM)