Nimrod Megiddo
Algorithmica
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
Ching-Tien Ho, Rakesh Agrawal, et al.
SIGMOD Record (ACM Special Interest Group on Management of Data)
Ronald Fagin, Joseph Y. Halpern, et al.
Information and Computation
Conference paper
An analysis of EUV resist stochastic printing failures
Martha I. Sanchez, Gregory M. Wallraff, et al.
EUVL 2019