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
Discrete and Computational Geometry
Nimrod Megiddo
Information Processing Letters
Nimrod Megiddo, Eitan Zemel
Journal of Algorithms