摘要： 多色点集划分研究如何将含有不同颜色点的平面划分为各个区域,每个区域中只包含一种颜色的点。这是计算几何中的一种组合优化问题。但是现有的多边形划分方式性能较差。为此,提出用直线来划分平面。针对平面上多色点集的直线划分,将其离散化,证明其可以被非确定性图灵机在多项式时间内判定。并将Max2SAT 问题在多项式时间内归约到组合优化问题,证明多色点集直线划分为NP 难,从而证明其是NP 完全的。利用最优化版本的特有性质,运用贪心方法构造出多项式时间的近似算法,并L 归约到Setcover 问题,以此证明算法的近似比为O(lgn)。
关键词:
计算几何,
计算复杂性,
近似算法,
划分算法,
组合优化,
NP 完全
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 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 O(lgn).
Key words:
computational geometry,
computational complexity,
approximation algorithm,
partition algorithm,
combinational optimization,
NP complete
中图分类号: