Publication
Discrete and Computational Geometry
Paper

On the complexity of polyhedral separability

Download paper

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.

Date

Publication

Discrete and Computational Geometry

Authors

Resources

Share