陈崇琛,Rudolf Fleischer

(复旦大学计算机科学技术学院,上海201203)

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

陈崇琛,Rudolf Fleischer

(复旦大学计算机科学技术学院,上海201203)

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

计算几何;计算复杂性;近似算法;划分算法;组合优化;NP完全

1 概述

在计算几何中有一类重要问题就是处理划分多色的点集[1-2]。多色点集划分问题是将平面上不同颜色的点集划分成单色的区域,已经被广泛研究[3]。研究这些问题对于数字信号中的噪声处理非常有用[4]。但是目前研究的问题大多是将不同颜色的点划分进不同的凸多边形,使得每个多边形内部都只有一种颜色[5],或者更加简单,不考虑多边形的凹凸[6]。

多色点集多边形划分目前较好的结果是达到最多O(n/c)个多边形可以划分平面,其中c为常数,n为输入规模[7]。但是对于n个点的点集,都能用n个多边形划分。其算法和朴素算法之间性能差异小,结果的复杂程度都和输入规模线性相关,且无法衡量解和最优解之间的差距。……