On the complexity of polyhedral separability (Q1119020)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexity of polyhedral separability |
scientific article |
Statements
On the complexity of polyhedral separability (English)
0 references
1988
0 references
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.
0 references
complexity
0 references
polyhedral separability
0 references
computational geometry
0 references
linear separability problem
0 references