多色点集直线划分的复杂性及其近似算法  

Complexity of Multi-colored Point Set Partition with Straight Line and Its Approximation Algorithm

作　　者：陈崇琛 Rudolf Fleischer 

机构地区：[1]复旦大学计算机科学技术学院,上海201203

出　　处：《计算机工程》2015年第2期298-302,共5页Computer Engineering

基　　金：上海市重点学科建设基金资助项目(B114);上海市科委科技基金资助项目(08DZ2271800;09DZ2272800)

摘　　要：多色点集划分研究如何将含有不同颜色点的平面划分为各个区域,每个区域中只包含一种颜色的点。这是计算几何中的一种组合优化问题。但是现有的多边形划分方式性能较差。为此,提出用直线来划分平面。针对平面上多色点集的直线划分,将其离散化,证明其可以被非确定性图灵机在多项式时间内判定。并将Max2SAT问题在多项式时间内归约到组合优化问题,证明多色点集直线划分为NP难,从而证明其是NP完全的。利用最优化版本的特有性质,运用贪心方法构造出多项式时间的近似算法,并L归约到Setcover问题,以此证明算法的近似比为O(lgn)。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 Max2 SAT problem to this problem in polynomial time,and proves that it is NP-hard.Then multicolored 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 0（lgn）.

关 键 词：计算几何 计算复杂性 近似算法 划分算法 组合优化 NP完全 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]