计算机工程Issue(2)：298-302,5.DOI:10.3969/j.issn.1000-3428.2015.02.057
多色点集直线划分的复杂性及其近似算法
Complexity of Multi-colored Point Set Partition with Straight Line and Its Approximation Algorithm
摘要
Abstract
Partitioning multi-colored point set into monochromatic parts is an optimization problem in computational geometry. It focuses on how to dissect the plan with polychrome points into regions with monochrome points. But the approach of partitioning with polygon cannot get good partition results now. This paper comes up with an approach of partitioning with straight line. This problem is discredited to prove that non-deterministic turing machine can decide this problem. It reduces Max2SAT problem to this problem in polynomial time,and proves that it is NP-hard. Then multi-colored point set is partitioned into monochromatic parts problem with straight line in NP-complete class. It gives an approximation algorithm for the optimization version by using L-reduction from Setcover problem, and proves the approximation ratio is O( lgn) .关键词
计算几何/计算复杂性/近似算法/划分算法/组合优化/NP完全Key words
computational geometry/computational complexity/approximation algorithm/partition algorithm/combinational optimization/NP complete分类
信息技术与安全科学引用本文复制引用
陈崇琛,Rudolf Fleischer..多色点集直线划分的复杂性及其近似算法[J].计算机工程,2015,(2):298-302,5.基金项目
上海市重点学科建设基金资助项目(B114) （B114）
上海市科委科技基金资助项目(08DZ2271800,09DZ2272800)。 （08DZ2271800,09DZ2272800）
