Edith Cohen, Nimrod Megiddo
Journal of the ACM (JACM)
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.
Edith Cohen, Nimrod Megiddo
Journal of the ACM (JACM)
Jun Rao, Chun Zhang, et al.
SIGMOD 2002
Nimrod Megiddo, Christos H. Papadimitriou
Theoretical Computer Science
Edith Cohen, Nimrod Megiddo
SODA 1991