Nimrod Megiddo, R. Chandrasekaran
Operations Research Letters
It is NP-complete to recognize whether two sets of points in general space can be separated by two hyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be separated with k lines. For every fixed k in any fixed dimension, it takes polynomial time to recognize whether two sets of points can be separated with k hyperplanes. © 1988 Springer-Verlag New York Inc.
Nimrod Megiddo, R. Chandrasekaran
Operations Research Letters
Shinji Mizuno, Nimrod Megiddo, et al.
Journal of Complexity
Edith Cohen, Nimrod Megiddo
Algorithmica
Edith Cohen, Nimrod Megiddo
SODA 1991