多色點集直線劃分的復(fù)雜性及其近似算法

陳崇琛,Rudolf Fleischer

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院,上海201203)

多色點集直線劃分的復(fù)雜性及其近似算法

陳崇琛,Rudolf Fleischer

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院,上海201203)

多色點集劃分研究如何將含有不同顏色點的平面劃分為各個區(qū)域,每個區(qū)域中只包含一種顏色的點。這是計算幾何中的一種組合優(yōu)化問題。但是現(xiàn)有的多邊形劃分方式性能較差。為此,提出用直線來劃分平面。針對平面上多色點集的直線劃分,將其離散化,證明其可以被非確定性圖靈機在多項式時間內(nèi)判定。并將Max2SAT問題在多項式時間內(nèi)歸約到組合優(yōu)化問題,證明多色點集直線劃分為NP難,從而證明其是NP完全的。利用最優(yōu)化版本的特有性質(zhì),運用貪心方法構(gòu)造出多項式時間的近似算法,并L歸約到Setcover問題,以此證明算法的近似比為O(lgn)。

計算幾何;計算復(fù)雜性;近似算法;劃分算法;組合優(yōu)化;NP完全

1 概述

在計算幾何中有一類重要問題就是處理劃分多色的點集[1-2]。多色點集劃分問題是將平面上不同顏色的點集劃分成單色的區(qū)域,已經(jīng)被廣泛研究[3]。研究這些問題對于數(shù)字信號中的噪聲處理非常有用[4]。但是目前研究的問題大多是將不同顏色的點劃分進不同的凸多邊形,使得每個多邊形內(nèi)部都只有一種顏色[5],或者更加簡單,不考慮多邊形的凹凸[6]。

多色點集多邊形劃分目前較好的結(jié)果是達到最多O(n/c)個多邊形可以劃分平面,其中c為常數(shù),n為輸入規(guī)模[7]。但是對于n個點的點集,都能用n個多邊形劃分。其算法和樸素算法之間性能差異小,結(jié)果的復(fù)雜程度都和輸入規(guī)模線性相關(guān),且無法衡量解和最優(yōu)解之間的差距。且結(jié)果復(fù)雜程度尚未考慮到多邊形本身邊數(shù)的復(fù)雜。于是提出新的劃分方法,采用直線劃分。多色點集直線劃分是用盡量少的直線(而非多邊形),將顏色混雜的平面劃分為單色的區(qū)域。

本文通過將其離散化,證明其可以被非確定性圖靈機在多項式時間內(nèi)判定,并從Max2SAT問題進行歸約,證明其NP完全的復(fù)雜性,并且提出一個高效的近似算法來解決這個問題。

2 相關(guān)定義

2.1 多色點集直線劃分

輸入平面上給定n個點,每個點都有一種顏色,總共有k種顏色。

輸出是否存在l條直線將平面分割成若干區(qū)域,使得每個區(qū)域中的點都具有相同顏色。

2.2 Max2SAT問題

輸入布爾子句集合C=(C1,C2,…,Cm),每個子句包含2個文字,集合中總共含有變量x1,x2,…,xn。

輸出給定k,是否存在一個賦值,使得C中至少有k個子句值為真。

2.3 L歸約

一個從問題A到問題B的L歸約是一對函數(shù)R和S,函數(shù)都能在對數(shù)空間內(nèi)計算,如果x是A的一個有最優(yōu)花費OPT(x)的實例,則R(x)是B的一個實例,其最優(yōu)花費滿足:

其中,α是一個正的常數(shù)。

如果s是R(x)的任意可行解,則S(s)是x的一個可行解,使得:

其中,β是另一個與歸約相關(guān)的正常數(shù);c表示2個實例的花費。

如果一個歸約能夠滿足L歸約的性質(zhì),那么這個歸約能夠保證問題的近似比[8]。

2.4 SETCOVER問題

輸入元素集合S={a1,a2,…,an},以及一個集合的集合A={A1,A2,…,Am},Ai是S的子集。

輸出,B是A的一個子集,使得S,且最小化。

3 復(fù)雜性

對于給定的問題實例,輸出為“是”當(dāng)且僅當(dāng)對于這個實例存在一個直線數(shù)目小于等于l的合法劃分,該劃分的每一條直線都非常接近輸入中的某2個點。接近的含義是,對于輸入中的任意點A,可以構(gòu)造點(xA,yA±ε),其中,xA,yA是點A的橫縱坐標(biāo)。如果輸入的點的橫縱坐標(biāo)都能用N個比特表示,那么ε是一個正常量,且ε＜1/(22N+1)。每一條劃分直線都經(jīng)過某2個新構(gòu)造的點。

證明:如果給定實例的答案是“是”,但是作為證據(jù)的劃分中存在某些線,至多接近輸入中的一個點。那么將這條線進行旋轉(zhuǎn),直到這條線接近某個輸入的點,然后以該點為中心進行旋轉(zhuǎn),直到接近輸入的另一個點,如圖1所示。

圖1 旋轉(zhuǎn)線的移動

圖2中的2個點,總共確定4條線,它們所劃分點的情況是不一樣的。

圖2 4條可行線的確定

如果給定實例中的l不小于n,那么問題的答案永遠(yuǎn)是“是”。在這個實例中,線數(shù)至多足以使每個區(qū)域只有一個點,自然是滿足單色要求的。可以用樸素的算法進行劃分。所以下面只考慮l小于n的情況。

引理1多色點集直線劃分問題在NP類中。

接下來證明問題是NP完全的。通過將Max2SAT問題在多項式時間內(nèi)歸約到多色點集直線劃分問題來證明。Max2SAT是一個著名的NP完全問題[9]。

定理多色點集直線劃分問題是NP完全的。

證明:給定一個Max2SAT的實例,將在多項式時間內(nèi)構(gòu)造一個多色點集直線劃分問題的實例。并且證明構(gòu)造的多色點集直線劃分問題的實例能夠被至多l(xiāng)條線劃分當(dāng)且僅當(dāng)給定的Max2SAT的實例存在一個賦值使得C中至少有l(wèi)b個子句為“真”。對于Max2SAT中的變量和子句構(gòu)造不同的零件,然后將這些零件在平面上拼起來,得到目標(biāo)中的多色點集直線劃分的實例。

對于Max2SAT中的每個變量構(gòu)造一個零件。一個變量零件包含a2+(a-1)2個小的菱形,2個對角線方向相鄰的菱形的顏色是不同的,且其相鄰的頂點非常接近,即2個頂點的距離不超過ε,ε的定義與觀察1中一樣。其中,a2個為其中一種顏色, (a-1)2個為另一種顏色,如圖3所示。如果想要用2(a-1)條直線來分割這個零件,只有2種可能的方式,如圖4所示。

圖3 變量零件

圖4 2種劃分變量零件的方式

考慮2個相鄰菱形的相鄰定點對,如果想要劃分整個零件,那么必須有一條直線通過這個相鄰異色頂點對。對于任意的線,至多通過2(a-1)個相鄰異色頂點對?？偣灿?2(a-1))2個相鄰異色頂點對。但是只有2(a-1)條直線,每條直線平均劃分(2(a-1))2/(2(a-1))=2(a-1)個相鄰異色頂點對,因此每條直線都劃分2(a-1)個相鄰異色頂點對。因此,劃分的直線一定是只有橫豎2種。假設(shè)得到的解中,既有橫的直線,也有豎的直線,那么必定有部分劃分的相鄰異色頂點對是重復(fù)的。2(a-1)條直線劃分的相鄰異色頂點對數(shù)小于(2(a-1))2,得到矛盾。于是得到上文的2種最優(yōu)劃分方式。

將其中一種劃分方式表示Max2SAT中的變量取值為“真”,稱之為“真劃分”;另一種劃分方式表示Max2SAT中的變量取值為“假”,稱之為“假劃分”。

圖5 構(gòu)造的細(xì)節(jié)

對于Max2SAT問題,假設(shè)不會存在一個子句同時包含x和?x,這些子句永遠(yuǎn)是為“真”?？梢栽谧鰵w約之前,在多項式時間內(nèi)去掉。取b=2。

下面情況之一發(fā)生,定義平面上零件發(fā)生相互影響:

(1)存在某條直線不屬于某個零件的“真劃分線”,或者“假劃分線”,但是卻劃分了屬于不同零件的2個以上相鄰異色點對。

(2)存在某條直線屬于某個子句零件的“真劃分線”或者“假劃分線”,但是卻劃分了其他子句零件中的相鄰異色點對,或者該子句中不包含的變量零件的相鄰異色點對。

(3)存在某條直線屬于某個變量零件的“真劃分線”或者“假劃分線”,但是卻劃分了其他變量零件或者不包含該變量的子句的零件。

引理2如果每個零件的劃分不會相互影響,那么原來的有n個變量和m個子句的Max2SAT問題實例能夠滿足至少lb個子句,當(dāng)且僅當(dāng)構(gòu)造的多色點集直線劃分問題實例能夠被至多l(xiāng)=2n(a-1)+ 2(m-lb)(b-1)條直線劃分。

證明:現(xiàn)在假定每個零件之間不會相互影響。

如果原來的有n個變量和m個子句的Max2SAT問題能夠滿足至少lb個子句,那么每個變量零件能夠被2(a-1)條線滿足,在劃分變量零件時順帶劃分的已經(jīng)滿足的子句零件就不需要重復(fù)劃分了,這部分的子句數(shù)目是lb,那么仍需要劃分的子句數(shù)目至多為m-lb,每個子句至多需要2(b-1)條直線來劃分,所以構(gòu)造的多色點集直線劃分問題實例至多需要被l=2n(a-1)+2(m-lb)(b-1)條直線劃分。

如果構(gòu)造的多色點集直線劃分實例能夠被至多l(xiāng)條直線劃分。因為零件之間不相互影響,所以劃分變量零件需要2n(a-1)條直線。故剩余l(xiāng)-2n(a-1)條直線來劃分子句零件。因此,至多(l-2n(a-1))/(2(b-1))個子句沒有被滿足,否則就有零件不能被劃分,故滿足的子句至少為lb=m-(l-2n(a-1))/(2(b-1))。

接下來說明如何設(shè)置a,b以及零件的位置,使得零件之間不會相互影響。

因為每條線由2個點決定,迭代添加變量零件(及相關(guān)的子句零件),每次添加時判斷是否存在相互影響,然后通過移動,去除相互影響。算法1是構(gòu)造算法:

在數(shù)學(xué)教學(xué)過程中，教師應(yīng)拓展游戲內(nèi)容，將生活中的數(shù)學(xué)元素融入到游戲教學(xué)中，拓展學(xué)生思維，豐富游戲內(nèi)容，使學(xué)生在游戲中學(xué)習(xí)到數(shù)學(xué)知識，并應(yīng)用于實際生活中。例如，在游戲教學(xué)中，教師可以組織學(xué)生玩兒老鷹捉小雞游戲，每當(dāng)老鷹捉住一只小雞時，教師可以向?qū)W生提問：雞媽媽現(xiàn)在還剩多少小雞。通過游戲的方式讓學(xué)生收獲知識，獲得快樂，生活與學(xué)習(xí)相結(jié)合，為學(xué)生創(chuàng)建輕松的學(xué)習(xí)環(huán)境，提升數(shù)學(xué)教學(xué)有效性[3]。

算法1計算零件位置的算法

可以看到函數(shù)addGadget最多被調(diào)用O(n)次。因此該規(guī)約的主要問題是證明addGadget函數(shù)的復(fù)雜性。

引理3函數(shù)addGadget每次執(zhí)行時間最多為O(nc),c為常數(shù),即多項式時間。

證明:顯然,在addGadget中的循環(huán)開始前,最多添加了O(nc1)個比特,c1為常數(shù),主要問題是循環(huán)迭代多少次才能結(jié)束。

在循環(huán)中,不斷將當(dāng)前的變量零件往縱坐標(biāo)正向移動。其余的子句零件也沿著其固有的方向移動。例如子句x∨y,假設(shè)已經(jīng)添加了x變量零件,正在添加y變量零件,那么該子句零件正沿著代表x取“真”的劃分線向縱向的正向移動。各個點的移動速度不同。

當(dāng)前最多有O(nc2)個相鄰異色頂點對,c2為常數(shù),2個相鄰異色頂點對所確定的直線數(shù)目為O(n2c2),2條直線最多相交一次,一個零件一條直線上移動最多需要O(n3c2)次就能保證當(dāng)前沒有零件相互影響。所以循環(huán)在多項式時間內(nèi)就能解決所有沖突并結(jié)束。

4 近似算法

將這個問題的最優(yōu)化版本通過L歸約,歸約到Setcover問題。Setcover問題已知有近似比為O(lg(n))的近似算法[10]。

引理4多色點集直線劃分問題能夠在多項式時間內(nèi)歸約到Setcover問題。

證明:給定一個多色點集直線劃分的實例。對于任意2個平面上的不同顏色的點pi,pj(i＜j),構(gòu)造一個元素aij,S是這些元素的集合。對于任意可行的直線lk,構(gòu)造一個S的子集Ak,這個集合包含代表這條直線所劃分的不同顏色點對的元素。總共有多項式個不同顏色的點對,多項式條可能的直線,每條直線劃分多項式個不同顏色的點對,所以這個構(gòu)造過程是多項式時間的。

引理5 這個歸約是L歸約。

證明:函數(shù)R是一個直線到子集的映射,S是一個子集到直線的映射,能夠在對數(shù)空間內(nèi)計算。且滿足:

所以其為L歸約。

根據(jù)L規(guī)約的性質(zhì),得到下面的定理:

定理2多色點集直線劃分有多項式時間的O(lg(n))-近似算法。

算法2O(lg(n))-近似算法

每次迭代查找有O(n2)條直線,最多可以迭代O(n2)次,因此算法復(fù)雜度為O(n4)。

5 結(jié)束語

本文給出了多色點集直線劃分問題的NP完全的復(fù)雜性證明,并且提出了一個多項式時間的O(lg(n))近似算法。該劃分相較多邊形的劃分,對于解有更好的理論保證,可以較好地劃分多色點集。在對于復(fù)雜性的證明中,只用到了2種顏色,這說明該問題極有可能不存在固定參數(shù)[11],至少顏色個數(shù)不是一個合適的參數(shù)。研究該問題在固定參數(shù)可解方面的復(fù)雜性是該問題的一個重要方向。另一方面,算法的時間復(fù)雜度仍然比較高,且沒有完全利用平面的性質(zhì),下一步方向是嘗試構(gòu)造平面的Voronoi圖[12],然后在近似算法中加入分治法來降低復(fù)雜度。

[1] Brass P,Moser W O J,Pach J.Research Problems in Discrete Geometry[M].[S.l.]:Springer,2005.

[2] Kaneko A,Kano M.Discrete Geometry on Red and Blue Points in the Plane Lattice[M].Berlin,Germany: Springer,2003.

[3] Ding Ren,Hosono K,Urabe M,et al.Partitioning a Planar Point Set into Empty Convex Polygons[C]// ProceedingsofConferenceonDiscreteand Computational Geometry.Berlin,Germany:Springer, 2003:129-134.

[4] Rosenfeld A.Picture Processing by Computer[J].ACM Computing Surveys,1969,1(3):147-176.

[5] Dumitrescu A,Kaye R.Matching Colored Points in the Plane:Some New Results[J].Computational Geometry, 2001,19(1):69-85.

[6] Atienza M N,Cortés C,Garijo D,et al.k-Factores en NubesBicromáticas[C]//ProceedingsofXII Encuentros de Geometria Computacional.Valladolid, Spain:[s.n.],2007:53-57.

[7] Dumitrescu A,Pach J.Partitioning Colored Point Sets into Monochromatic Parts[J].International Journal of Computational Geometry&Applications,2002,12(5): 401-412.

[8] 堵丁柱,葛可一,胡曉東.近似算法的設(shè)計與分析[M].北京:高等教育出版社,2011.

[9] Papadimitriou C H.Computational Complexity[M]. [S.l.]:Addison-Wesley,1993.

[10] Cormen T H,Leiserson C E.算法導(dǎo)論[M].2版.北京:機械工業(yè)出版社,2006.

[11] Cai Liming,Chen J.On Fixed-parameter Tractability and Approximability of NP Optimization Problems[J]. Journal of Computer and System Sciences,1997,54(3): 465-474.

[12] Aurenhammer F.Voronoi Diagrams——A Survey of a FundamentalGeometricDataStructure[J].ACM Computing Surveys,1991,23(3):345-405.

編輯 顧逸斐

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

CHEN Chongchen,Rudolf Fleischer
(School of Computer Science,Fudan University,Shanghai 201203,China)

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 usingL-reduction from Setcover problem,and proves the approximation ratio isO(lgn).

computationalgeometry;computationalcomplexity;approximationalgorithm;partitionalgorithm; combinational optimization;NP complete

陳崇琛,Rudolf Fleischer.多色點集直線劃分的復(fù)雜性及其近似算法[J].計算機工程,2015,41(2): 298-302.

英文引用格式:Chen Chongchen,Rudolf Fleische.Complexity of Multi-colored Point Set Partition with Straight Line and Its Approximation Algorithm[J].Computer Engineering,2015,41(2):298-302.

1000-3428(2015)02-0298-05

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.02.057

上海市重點學(xué)科建設(shè)基金資助項目(B114);上海市科委科技基金資助項目(08DZ2271800,09DZ2272800)。

陳崇琛(1989-),男,碩士研究生,主研方向:計算幾何,計算復(fù)雜性;Rudolf Fleischer,教授。

2014-03-21

:2014-04-14E-mail:chenkov@yeah.net