On the complexity of polyhedral separability (Q1119020)

Zwei endliche Punktmengen P,Q in \({\mathbb{R}}^ d\) können durch k Hyperebenen getrennt werden, wenn es k Hyperebenen so gibt, daß jedes Punktepaar \(p\in P\), \(q\in Q\) durch mindestens eine der k Hyperebenen getrennt wird. Zu erkennen, ob zwei endliche Punktmengen in \({\mathbb{R}}^ d\) durch 2 Hyperebenen getrennt werden können, ist NP-vollständig. Zu erkennen, ob zwei endliche Punktmengen in \({\mathbb{R}}^ 2\) durch k Geraden getrennt werden können, ist NP-vollständig. Für festes k und d braucht es polynomiale Zeit, um festzustellen, ob zwei endliche Punktmengen, in \({\mathbb{R}}^ d\) durch k Hyperebenen getrennt werden können.