On the complexity of polyhedral separability |
| |
| Authors: | Nimrod Megiddo |
| |
| Affiliation: | (1) IBM Almaden Research Center, 95120-6099 San Jose, CA, USA;(2) Tel Aviv University, Tel Aviv, Israel |
| |
| 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 withk lines. For every fixedk in any fixed dimension, it takes polynomial time to recognize whether two sets of points can be separated withk hyperplanes. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
