Rafael Hassin, Nimrod Megiddo
Linear Algebra and Its Applications
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.
Rafael Hassin, Nimrod Megiddo
Linear Algebra and Its Applications
Moritz Hardt, Nimrod Megiddo, et al.
ITCS 2016
Edith Cohen, Nimrod Megiddo
SODA 1991
Dorit S. Hochbaum, Nimrod Megiddo, et al.
Mathematical Programming