Conference paper
Dynamic faceted search for discovery-driven analysis
Debabrata Dash, Jun Rao, et al.
CIKM 2008
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
Algorithmica
Ronald Fagin, Joseph Y. Halpern, et al.
Information and Computation
Tomás Feder, Nimrod Megiddo, et al.
Theoretical Computer Science