Masakazu Kojima, Nimrod Megiddo
Linear Algebra and Its Applications
Paper
On the complexity of polyhedral separability
Abstract
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.
Related
Edith Cohen, Nimrod Megiddo
Mathematical Programming
Daphne Koller, Nimrod Megiddo, et al.
Games and Economic Behavior
Nimrod Megiddo, Christos H. Papadimitriou
Theoretical Computer Science