|
|||||
|
|
| 多色点集直线划分的复杂性及其近似算法 | |
| 引用本文： | 陈崇琛.多色点集直线划分的复杂性及其近似算法[J].计算机工程,2015(2). |
| 作者姓名： | 陈崇琛 |
| 作者单位： | 复旦大学计算机科学技术学院,上海,201203 |
| 基金项目： | 上海市重点学科建设基金资助项目，上海市科委科技基金资助项目(08DZ2271800 |
| 摘 要： | 多色点集划分研究如何将含有不同颜色点的平面划分为各个区域，每个区域中只包含一种颜色的点。这是计算几何中的一种组合优化问题。但是现有的多边形划分方式性能较差。为此，提出用直线来划分平面。针对平面上多色点集的直线划分，将其离散化，证明其可以被非确定性图灵机在多项式时间内判定。并将Max2SAT问题在多项式时间内归约到组合优化问题，证明多色点集直线划分为NP难，从而证明其是NP完全的。利用最优化版本的特有性质，运用贪心方法构造出多项式时间的近似算法，并L归约到Setcover问题，以此证明算法的近似比为O( lgn)。 |
| 关 键 词： | 计算几何 计算复杂性 近似算法 划分算法 组合优化 NP完全 |
Complexity of Multi-colored Point Set Partition with Straight Line and Its Approximation Algorithm |
|
| CHEN Chongchen,Rudolf Fleischer.Complexity of Multi-colored Point Set Partition with Straight Line and Its Approximation Algorithm[J].Computer Engineering,2015(2). | |
| Authors: | CHEN Chongchen Rudolf Fleischer |
| Abstract: | |
| Keywords: | computational geometry computational complexity approximation algorithm partition algorithm combinational optimization NP complete |
| 本文献已被 万方数据 等数据库收录！ | |