陳崇琛,Rudolf Fleischer

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

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

陳崇琛,Rudolf Fleischer

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

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

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

1 概述

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

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

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

2 相關(guān)定義

2.1 多色點(diǎn)集直線劃分

輸入平面上給定n個(gè)點(diǎn),每個(gè)點(diǎn)都有一種顏色,總共有k種顏色。

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

2.2 Max2SAT問(wèn)題

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

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

2.3 L歸約

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

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

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

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

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

2.4 SETCOVER問(wèn)題

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

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

3 復(fù)雜性

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

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

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

圖2中的2個(gè)點(diǎn),總共確定4條線,它們所劃分點(diǎn)的情況是不一樣的。

圖2 4條可行線的確定

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

引理1多色點(diǎn)集直線劃分問(wèn)題在NP類中。

接下來(lái)證明問(wèn)題是NP完全的。通過(guò)將Max2SAT問(wèn)題在多項(xiàng)式時(shí)間內(nèi)歸約到多色點(diǎn)集直線劃分問(wèn)題來(lái)證明。Max2SAT是一個(gè)著名的NP完全問(wèn)題[9]。

定理多色點(diǎn)集直線劃分問(wèn)題是NP完全的。

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

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

圖3 變量零件

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

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

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

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

對(duì)于Max2SAT問(wèn)題,假設(shè)不會(huì)存在一個(gè)子句同時(shí)包含x和?x,這些子句永遠(yuǎn)是為“真”。可以在做歸約之前,在多項(xiàng)式時(shí)間內(nèi)去掉。取b=2。

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

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

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

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

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

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

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

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

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

因?yàn)槊織l線由2個(gè)點(diǎn)決定,迭代添加變量零件(及相關(guān)的子句零件),每次添加時(shí)判斷是否存在相互影響,然后通過(guò)移動(dòng),去除相互影響。算法1是構(gòu)造算法:

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

算法1計(jì)算零件位置的算法

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

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

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

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

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

4 近似算法

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

引理4多色點(diǎn)集直線劃分問(wèn)題能夠在多項(xiàng)式時(shí)間內(nèi)歸約到Setcover問(wèn)題。

證明:給定一個(gè)多色點(diǎn)集直線劃分的實(shí)例。對(duì)于任意2個(gè)平面上的不同顏色的點(diǎn)pi,pj(i＜j),構(gòu)造一個(gè)元素aij,S是這些元素的集合。對(duì)于任意可行的直線lk,構(gòu)造一個(gè)S的子集Ak,這個(gè)集合包含代表這條直線所劃分的不同顏色點(diǎn)對(duì)的元素?？偣灿卸囗?xiàng)式個(gè)不同顏色的點(diǎn)對(duì),多項(xiàng)式條可能的直線,每條直線劃分多項(xiàng)式個(gè)不同顏色的點(diǎn)對(duì),所以這個(gè)構(gòu)造過(guò)程是多項(xiàng)式時(shí)間的。

引理5 這個(gè)歸約是L歸約。

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

所以其為L(zhǎng)歸約。

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

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

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

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

5 結(jié)束語(yǔ)

本文給出了多色點(diǎn)集直線劃分問(wèn)題的NP完全的復(fù)雜性證明,并且提出了一個(gè)多項(xiàng)式時(shí)間的O(lg(n))近似算法。該劃分相較多邊形的劃分,對(duì)于解有更好的理論保證,可以較好地劃分多色點(diǎn)集。在對(duì)于復(fù)雜性的證明中,只用到了2種顏色,這說(shuō)明該問(wèn)題極有可能不存在固定參數(shù)[11],至少顏色個(gè)數(shù)不是一個(gè)合適的參數(shù)。研究該問(wèn)題在固定參數(shù)可解方面的復(fù)雜性是該問(wèn)題的一個(gè)重要方向。另一方面,算法的時(shí)間復(fù)雜度仍然比較高,且沒(méi)有完全利用平面的性質(zhì),下一步方向是嘗試構(gòu)造平面的Voronoi圖[12],然后在近似算法中加入分治法來(lái)降低復(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è)計(jì)與分析[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版.北京:機(jī)械工業(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.多色點(diǎn)集直線劃分的復(fù)雜性及其近似算法[J].計(jì)算機(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

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

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

2014-03-21

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