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

摘要：

多色点集划分研究如何将含有不同颜色点的平面划分为各个区域，每个区域中只包含一种颜色的点。这是计算几何中的一种组合优化问题。但是现有的多边形划分方式性能较差。为此，提出用直线来划分平面。针对平面上多色点集的直线划分，将其离散化，证明其可以被非确定性图灵机在多项式时间内判定。并将Max2SAT问题在多项式时间内归约到组合优化问题，证明多色点集直线划分为NP难，从而证明其是NP完全的。利用最优化版本的特有性质，运用贪心方法构造出多项式时间的近似算法，并L归约到Setcover问题，以此证明算法的近似比为O( lgn)。

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

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2015-03-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：298-302