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

• 作者: Rudolf Fleischer 陈崇琛
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 计算几何 计算复杂性 近似算法 划分算法 组合优化 NP完全
• 年，卷（期）: 2015,（2）
• 页码范围: 298-302
• 页数: 5页
• 分类号: TP301.6
• 字数: 4693字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2015.02.057

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈崇琛	复旦大学计算机科学技术学院	1	0	0.0	0.0
2	Rudolf Fleischer	复旦大学计算机科学技术学院	4	4	1.0	2.0