Daniela Pucci De Farias, Nimrod Megiddo
Journal of the ACM
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.
Daniela Pucci De Farias, Nimrod Megiddo
Journal of the ACM
Masakazu Kojima, Nimrod Megiddo, et al.
Mathematical Programming
Nimrod Megiddo, Arie Tamir
Operations Research Letters
Edith Cohen, Nimrod Megiddo
SODA 1991