高犇

(太原理工大學(xué)數(shù)學(xué)學(xué)院,山西 太原 030024)

刻畫排列的連通分支

高犇

(太原理工大學(xué)數(shù)學(xué)學(xué)院,山西 太原 030024)

應(yīng)用柱代數(shù)分解算法和簡(jiǎn)化的胞腔相鄰算法,得到一個(gè)刻畫R3中由n個(gè)緊半代數(shù)集所組成排列連通分支的算法.

連通分支;緊半代數(shù)集;柱代數(shù)分解;胞腔相鄰

1 引言

在固定維數(shù)歐幾里得空間中幾何對(duì)象的排列是計(jì)算幾何和計(jì)算機(jī)修復(fù)幾何設(shè)計(jì)中的基本對(duì)象[1].通常假定在這樣一個(gè)排列中每個(gè)對(duì)象有個(gè)簡(jiǎn)單的描述,例如,它們是由固定次數(shù)的一些多項(xiàng)式所定義的半代數(shù)集.在三維空間中,二次曲面所形成的排列是特別重要的,因?yàn)樗鼈儽粡V泛的應(yīng)用于CAD/CAM,計(jì)算機(jī)圖表,機(jī)器人學(xué)[2]以及計(jì)算物理學(xué)[3-4]等相當(dāng)多的學(xué)科中.因此,在R3中,計(jì)算和刻畫緊半代數(shù)集所形成排列的連通分支是很必要的.

在計(jì)算半代數(shù)集所形成排列拓?fù)湫再|(zhì)的許多算法中包含一個(gè)基本的組成部分,即柱代數(shù)分解算法[5],柱代數(shù)分解算法能把一個(gè)給定的半代數(shù)集分解成一些拓?fù)浒?從而可以計(jì)算一個(gè)半代數(shù)集的三角剖分[6],從這個(gè)三角剖分可以計(jì)算半代數(shù)集的連通分支,同調(diào)群等.但做柱代數(shù)分解時(shí)有一個(gè)缺點(diǎn),即要使用迭代投影(即在柱代數(shù)分解的過程中每一步維數(shù)要減少1),并且多項(xiàng)式的數(shù)目在每一步過程中都會(huì)平方一次.因此,柱代數(shù)分解算法的復(fù)雜度是雙指數(shù)的,這樣在大多數(shù)情況下使得計(jì)算排列拓?fù)湫畔⑹遣粚?shí)際的.然而,對(duì)于低維的一些重要問題使用柱代數(shù)分解算法還是很有效的.

從柱代數(shù)分解算法中,能夠獲得胞腔相鄰[7-8]的重要信息.非正式地講,在Rn(n≥1)中,兩個(gè)不相交的胞腔如果相互接觸,則這兩個(gè)胞腔是相鄰的;正式的講,如果兩個(gè)胞腔的并是連通的,則這兩個(gè)胞腔是相鄰的.相鄰信息是關(guān)于柱代數(shù)分解一些應(yīng)用中的必要組成部分.例如,對(duì)于n=2和n=3,一個(gè)柱形分解構(gòu)造算法已經(jīng)被改進(jìn),可以使用相鄰信息去規(guī)避原始算法[9]的某些時(shí)間耗散的步驟.Schwartz和Sharir應(yīng)用胞腔相鄰去研究運(yùn)動(dòng)問題[10],同樣地, Arnon和McCallum在其算法中去求一條實(shí)代數(shù)曲線的拓?fù)漕愋蚚11].

本文中,應(yīng)用柱代數(shù)分解算法和簡(jiǎn)化的胞腔相鄰算法,得到一個(gè)刻畫中由n個(gè)緊半代數(shù)集所組成排列中連通分支的算法.這個(gè)算法沒有使用三角剖分.代替地,計(jì)算局部柱代數(shù)分解.在算法第2步,僅僅計(jì)算了部分胞腔相鄰信息,并沒有使用所有的胞腔相鄰信息.本文的胞腔相鄰算法比文獻(xiàn)[7-8]中在平面和中求胞腔相鄰的算法有所簡(jiǎn)化.并且為了刻畫連通分支,本文中這些胞腔相鄰算法的輸入是(i=2,3)中的兩個(gè)柱形區(qū)域或一個(gè)柱代數(shù)分解,而且在平面中沒有退化的0-胞腔(參看文獻(xiàn)[8]中定義).更多的,本文中胞腔相鄰算法的過程比在文獻(xiàn)[7-8]中算法的過程有所改進(jìn).

本文其它部分內(nèi)容如下,第1節(jié)論述關(guān)于柱代數(shù)分解算法的預(yù)備知識(shí).第2節(jié)論述平面和中的簡(jiǎn)化胞腔相鄰算法.第3節(jié)提出一個(gè)在中刻畫n個(gè)緊半代數(shù)集所組成排列中連通分支的算法.第4節(jié)對(duì)本文進(jìn)行總結(jié)并對(duì)將來的工作提出一些想法.

2 柱代數(shù)分解算法的預(yù)備知識(shí)

本小節(jié)中,先介紹柱代數(shù)分解算法.對(duì)于柱代數(shù)分解更詳細(xì)的內(nèi)容請(qǐng)看文獻(xiàn)[5-6,12-13].

輸入有限多項(xiàng)式集

輸出的F-符號(hào)不變柱代數(shù)分解及其代表系.

(1)如果n=1,求出多項(xiàng)式集F的各個(gè)多項(xiàng)式的所有實(shí)根r1

求出∏(F)在Γ′上的實(shí)根函數(shù)

(3)由此得到F-符號(hào)不變柱代數(shù)分解和它的代表系:

定義 2.1給定上的一個(gè)多項(xiàng)式有限集合?,中的一個(gè)子集S稱為?-不變的,如果?中每個(gè)多項(xiàng)式P在S上是不變號(hào)的.如果關(guān)于的一個(gè)柱代數(shù)分解中的每個(gè)胞腔都是?-不變的,那么這個(gè)柱代數(shù)分解稱為適應(yīng)于?.

下面做對(duì)適應(yīng)于單位球面的柱代數(shù)分解.

從柱代數(shù)分解算法中需要獲得關(guān)于胞腔相鄰[7-8]的重要信息.換言之,對(duì)某個(gè)柱代數(shù)分解中的兩個(gè)胞腔,需要知道一個(gè)胞腔的閉包是否與另一個(gè)相交.例如,以上例子中,點(diǎn)(1,0,0)所對(duì)應(yīng)的胞腔相鄰于胞腔

在第2節(jié)中將要給出關(guān)于胞腔相鄰更多的細(xì)節(jié).

圖1 適應(yīng)于單位球面的柱代數(shù)分解

3 胞腔相鄰

3.1 預(yù)備知識(shí)

對(duì)于適應(yīng)于多項(xiàng)式所組成一個(gè)有限集合?的一個(gè)柱代數(shù)分解,為了描述獲得所需胞腔相鄰信息的方法,需要下面的內(nèi)容.

更多地,可以直觀地對(duì)胞腔進(jìn)行如下標(biāo)記.

對(duì)于R上的一個(gè)胞腔標(biāo)記為Ci,當(dāng)這個(gè)胞腔在一維數(shù)軸上從左到右數(shù)時(shí)為第i個(gè)胞腔.

更多地,定義關(guān)于柱代數(shù)分解中的i-胞腔,(0≤i≤3)是指i-維胞腔.在一個(gè)柱代數(shù)分解中一個(gè)l-胞腔和一個(gè)k-胞腔的相鄰定義為{l,k}-相鄰.

C2代表點(diǎn) ?1, C3代表集合 {x|?1

C2,1與C2,2為inter-stack胞腔相鄰,C2,2與C3,2為intra-stack胞腔相鄰;C2,2,2與C3,2,2為{0,1}-相鄰.

在本文中,僅考慮緊半代數(shù)集Si,等價(jià)地,

deg(Pi,j(x,y,z))=2,并且,?∈{≤,=}.下面的內(nèi)容將要給出,在和中,適合于這種情況的柱代數(shù)分解中胞腔相鄰算法.由于在文獻(xiàn)[7-8]中主要算法結(jié)果的正確性,不難推出本文中關(guān)于胞腔相鄰算法的正確性是顯然的.具體詳情請(qǐng)看文獻(xiàn)[7-8].

在每一個(gè)柱形區(qū)域中,通過從下向上標(biāo)記胞腔可以得到這個(gè)柱形區(qū)域中所有的 intrastack相鄰信息.例如,胞腔Ci,j相鄰于胞腔Ci,j+1.因此,為了得到關(guān)于的一個(gè)柱代數(shù)分解中的胞腔相鄰信息,主要是確定inter-stack相鄰信息.在R2中,通過利用{0,1}-inter-stack相鄰信息和intra-stack相鄰信息,就能確定關(guān)于R2的一個(gè)柱代數(shù)分解中所有其它胞腔相鄰的信息.例如,假定Ci,j是一個(gè) 2-胞腔,包含在以 1-胞腔 Ci為基礎(chǔ)的柱形區(qū)域中,并且下面和上面分別被兩個(gè) 1-胞腔 Ci,j?1和 Ci,j+1所界定,其中 Ci,j?1和 Ci,j+1分別相鄰于 0-胞腔 Ci?1,k1和 0-胞腔 Ci?1,k2(k1≤k2),并且這兩個(gè)0-胞腔包含在以 0-胞腔 Ci?1為基礎(chǔ)的柱形區(qū)域中,那么,Ci,j相鄰于這個(gè)柱形區(qū)域中介于胞腔Ci?1,k1和胞腔Ci?1,k2之間所有的胞腔,并且在這個(gè)柱形區(qū)域中僅僅與這些胞腔相鄰.因此,只要得到中的{0,1}-inter-stack相鄰信息,就能獲得所有的inter-stack相鄰信息.下面的算法給出了關(guān)于的一個(gè)柱代數(shù)分解中{0,1}-inter-stack相鄰信息的描述.

算法 1

輸入關(guān)于的一個(gè)柱代數(shù)分解中分別以0-胞腔c0=(α,0)和1-胞腔

為基礎(chǔ)的2個(gè)柱形區(qū)域A和B,其中c0相鄰于c1.

輸出L1是柱形區(qū)域A和B之間所有{0,1}-inter-stack相鄰信息的表.

1.令L1←?.求柱形區(qū)域A中的0-胞腔

得到

2.如果有一個(gè) sj,0≤j≤m,使得 y=yj與柱形區(qū)域 B中的某個(gè) 1-胞腔相交,令u←直到y(tǒng)=yj與以{(x,y)|α

3.令柱形區(qū)域A中的±∞-截面分別相鄰于柱形區(qū)域B中的±∞-截面.在柱形區(qū)域B中從下向上求1-胞腔,···,(l≥0).對(duì)j=1,···,m做以下3步:

3.1.令n←0和nj←是x=u與柱形區(qū)域B中介于y=yj?1和y=yj之間1-胞腔的相交數(shù)目.

3.2.在L1中,柱形區(qū)域A中的0-胞腔相鄰于柱形區(qū)域B中的1-胞腔,···.

3.3.令n←n+nj.

如果c0在c1的右邊,重復(fù)算法1.

算法 2

輸入關(guān)于的一個(gè)柱代數(shù)分解.

輸出I是這個(gè)柱代數(shù)分解中所有胞腔的指標(biāo)表.L是這個(gè)柱代數(shù)分解中所有胞腔相鄰信息的表.

1.令I(lǐng)←?.令L←?.構(gòu)造柱代數(shù)分解(平面)所誘導(dǎo)的柱代數(shù)分解(線)中的胞腔指標(biāo)Ci,(1≤i≤2n+1,n≥0).對(duì)i=1,···,2n+1做以下2步:

2.2.記錄這個(gè)柱形區(qū)域中intra-stack相鄰信息到L中.

2.對(duì)i=1,···,2n,利用算法1,輸入分別以Ci和Ci+1為基礎(chǔ)的2個(gè)柱形區(qū)域,然后添加輸出L1到L中(注意,由算法1所輸出的胞腔相鄰信息中的胞腔必須首先轉(zhuǎn)換成關(guān)于的柱代數(shù)分解中所對(duì)應(yīng)的胞腔指標(biāo)).

3.正如第2.2節(jié)中第2段所述,使用目前L中的信息可以推出關(guān)于的這個(gè)柱代數(shù)分解中其它inter-stack相鄰信息,然后添加到L中.

算法 3

輸入關(guān)于的一個(gè)柱代數(shù)分解中的2個(gè)柱形區(qū)域A和B,并且A和B分別是以中的一個(gè)0-胞腔c0=(α,β),α,β∈R和一個(gè)1-胞腔c1為基礎(chǔ)的柱形區(qū)域,其中c0相鄰于c1. p=(ρ,σ),(ρ,σ∈是c1中的一個(gè)樣本點(diǎn).F(x,y,z)∈[x,y,z]使得H(z)=F(α,β,z)的根定義柱形區(qū)域A,F(ρ,σ,z)的根定義柱形區(qū)域B.G(x,y)∈(x,y)關(guān)于x或y或兩個(gè)的次數(shù)是正的.c1和c0包含在Zero(G(x,y))(即G(x,y)實(shí)根的集合)中.

輸出L是柱形區(qū)域A和B之間所有的{0,1}-inter-stack相鄰信息表.

1.如果 degy(G)>0,然后令 P(x,z)← Resy(G,F)(F和 G關(guān)于 y的結(jié)式),否則如果degx(G)>0,然后令P(y,z)←Resx(G,F)(F和G關(guān)于x的結(jié)式).不失一般性,從現(xiàn)在開始假定G關(guān)于y的次數(shù)是正的,并且c1在c0的右邊,因此在這步計(jì)算P(x,z).

2.令 J=Proj({P(x,z)}).求 J中元素的實(shí)根,得到 b∈使得 P定義 2個(gè)分別以 (α,0)和 {(x,z)|α

3.1.縮小關(guān)于這個(gè)根的孤立區(qū)間直到這個(gè)區(qū)間只與P(?b,z)的一個(gè)根的唯一孤立區(qū)間相交,獲得s1唯一的投影1-胞腔t1;

3.2.令 t0是柱形區(qū)域 A′中 t1唯一的邊界 0-胞腔 (從 L1中獲得),然后縮小關(guān)于P(α,z)和H(z)的根的孤立區(qū)間直到對(duì)應(yīng)于t0的關(guān)于P(α,z)的根的孤立區(qū)間與H(z)的一個(gè)根的唯一孤立區(qū)間相交,即求出了柱形區(qū)域A中s1的邊界0-胞腔.

算法 4

輸入關(guān)于的一個(gè)柱代數(shù)分解中的2個(gè)柱形區(qū)域A和B,并且A和B分別是以中的一個(gè)1-胞腔c1和一個(gè)2-胞腔c2為基礎(chǔ)的柱形區(qū)域,其中c1相鄰于c2.

輸出L是柱形區(qū)域A和B之間所有的{1,2}-inter-stack相鄰信息表.

1.如果關(guān)于R的誘導(dǎo)柱代數(shù)分解中存在一個(gè)1-胞腔

使得c1和c2包含在以c′為基礎(chǔ)的柱形區(qū)域中,并且c2在c1的上面(下面).令是c′中的樣本點(diǎn),計(jì)算

得到關(guān)于R2的一個(gè)柱代數(shù)分解中的2個(gè)柱形區(qū)域A′和B′,并且這2個(gè)柱形區(qū)域分別以0-胞腔和1-胞腔

為基礎(chǔ).利用算法1,輸入A′和B′,得到輸出L′,然后添加L′到L.

否則2.如果關(guān)于R的誘導(dǎo)柱代數(shù)分解中存在一個(gè)0-胞腔c0=(α1,0),(α1∈)使得c1包含在以c0為基礎(chǔ)的柱形區(qū)域中,并且c2在c1的右面(左面).令(α1,β),(β∈)是c1中的樣本點(diǎn),計(jì)算{(x,y)|α1

如果c0和c2是關(guān)于的一個(gè)柱代數(shù)分解中的一個(gè)0-胞腔和一個(gè)2-胞腔,并且c0相鄰于c2,那么恰好在關(guān)于的這個(gè)柱代數(shù)分解中存在2個(gè)1-胞腔使得同時(shí)相鄰于c0和c2.

算法 5

輸入關(guān)于的一個(gè)柱代數(shù)分解中的2個(gè)柱形區(qū)域A和B,并且A和B分別是以中的一個(gè)0-胞腔c0=(α,β),α,β∈和一個(gè)2-胞腔c2為基礎(chǔ)的柱形區(qū)域,其中c0相鄰于c2.

輸出L是柱形區(qū)域A和B之間所有的{0,2}-inter-stack相鄰信息表.

1.選擇一個(gè)1-胞腔c1,使得c1同時(shí)相鄰于c0和c2.

2.對(duì)柱形區(qū)域B中的每個(gè)2-胞腔s2,利用算法4,從以c1為基礎(chǔ)的柱形區(qū)域中得到s2的邊界1-胞腔t1.

3.利用算法3,從柱形區(qū)域A中得到t1的邊界0-胞腔t0.那么對(duì)于t1而言,{t0,s2}是柱形區(qū)域A和B之間唯一的{0,2}-inter-stack相鄰,添加它到L中.

算法 6

輸入關(guān)于的一個(gè)柱代數(shù)分解.

輸出I是這個(gè)柱代數(shù)分解中所有胞腔的指標(biāo)表.L是這個(gè)柱代數(shù)分解中所有胞腔相鄰信息的表.

1.令 I←?.令 L←?.利用算法 2,輸入關(guān)于這個(gè)柱代數(shù)分解 ()誘導(dǎo)的柱代數(shù)分解(平面上),獲得關(guān)于誘導(dǎo)柱代數(shù)分解(平面上)的輸出I′和L′.對(duì)每個(gè)胞腔Ci,j做以下2步:

1.2.記錄這個(gè)柱形區(qū)域中的intra-stack相鄰信息到L中.

2.對(duì)L′中的每對(duì)相鄰胞腔{c,d},根據(jù)c和d的維數(shù),選擇以下3種情況中的一種,在這個(gè)柱代數(shù)分解(R3)中求以這2個(gè)相鄰胞腔為基礎(chǔ)的柱形區(qū)域之間的某些inter-stack相鄰信息.

2.1.令 c0=(α,β),α,β∈和 c1是一對(duì)相鄰胞腔.令關(guān)于的這個(gè)柱代數(shù)分解中以 c0和 c1為基礎(chǔ)的 2個(gè)柱形區(qū)域分別是 A和 B.令 p=(ρ,σ),ρ,σ∈是 c1中的樣本點(diǎn),H(z)=F(α,β,z)的根定義柱形區(qū)域A,F(ρ,σ,z)的根定義柱形區(qū)域B.令c0和c1包含在Zero(G(x,y))中.利用算法3,輸入c0,c1,A,B,p,H(z),F(α,β,z)和G(x,y),得到輸出L?.注意,在修改L?中元素的指標(biāo)后,添加它們到L中.

2.2.令c1和c2是一對(duì)相鄰胞腔.令關(guān)于的這個(gè)柱代數(shù)分解中以c1和c2為基礎(chǔ)的2個(gè)柱形區(qū)域分別是A和B.利用算法4,輸入A,B,c1和c2,得到輸出L?.注意,在修改L?中元素的指標(biāo)后,添加它們到L中.

2.3.令c0和c2是一對(duì)相鄰胞腔.令關(guān)于的這個(gè)柱代數(shù)分解中以c0和c2為基礎(chǔ)的2個(gè)柱形區(qū)域分別是A和B.利用算法5,輸入A,B,c0和c2,得到輸出L?.添加L?中的元素到L中.

3.使用L中現(xiàn)有的內(nèi)容推出關(guān)于這個(gè)柱代數(shù)分解其它的inter-stack相鄰信息.添加它們到L中.

3 刻畫連通分支

這些胞腔包含在S中,并且在這個(gè)柱代數(shù)分解中只有這些胞腔包含在S中.更多地,C2,2,2相鄰于,,和;相鄰于,和;相鄰于, C3,3,4和C4,2,2;C4,2,2相鄰于C3,3,2和C3,3,4.所以S是半代數(shù)連通的,即在S中僅有一個(gè)連通分支.這個(gè)連通分支能被刻畫為:

下面給出刻畫連通分支的算法.

算法 7

輸入中 n個(gè)緊半代數(shù)集的并集 S,其中每個(gè)集合 Si,(1≤i≤n)由有限個(gè)集合的并集所定義,其中

輸出S中連通分支的刻畫D.

1.對(duì)每個(gè)

做以下4步:

1.1.計(jì)算適應(yīng)于集合{Si,1,···,Si,ki}的一個(gè)柱代數(shù)分解.

1.2.利用算法6,輸入這個(gè)柱代數(shù)分解,得關(guān)于此柱代數(shù)分解中所有胞腔相鄰信息的表.

1.3.確定這個(gè)柱代數(shù)分解中所有包含于Si的胞腔.

1.4.刻畫Si中所有的連通分支{,,···,}.

2.對(duì){S11,1,S11,2,···,}和{,,···,},做以下幾步:

2.1.令

2.1.1.搜索 {S1,α1,···,S1,αw}? {S1,p1{,···,S1,pe},滿足 S1,α1∩[ξ,η]×??,···, S1,αw∩[ξ,η]×??.{S2,β1,···,S2,βv}?S2,q1,···,S2,qf},滿足

2.1.2.求適應(yīng)于集合{S1,α1,···,S1,αw,S2,β1,···,S2,βv}的一個(gè)柱代數(shù)分解.

2.1.3.利用算法6,輸入這個(gè)柱代數(shù)分解,得關(guān)于這個(gè)柱代數(shù)分解中所有包含于[ξ,η]×的胞腔相鄰信息的表.

2.2.由第 2.1步中的內(nèi)容,得到 S1∪S2中所有連通分支 {,,···,}的刻畫.令S1←S1∪S2.

3.對(duì){S12,1,S12,2,···,}和{S31,1,S31,2,···,},重復(fù)第 2步,得到 S1∪S3中所有連通分支{,,···,}的刻畫.令S1←S1∪S3.

4.重復(fù)第3步,得到S1∪Sr,(3≤r≤n)中所有連通分支{,,···,}的刻畫.添加S=S1∪Sn中所有連通分支{,,···,}的刻畫到D中.

算法 7的正確性由柱代數(shù)分解算法和前面胞腔相鄰算法的正確性所保證.注意,在算法7中的每1步,通過計(jì)算適應(yīng)于在R[x1,x2,x3]中一個(gè)有限多項(xiàng)式集的柱代數(shù)分解和使用算法6,能確定所有包含于上面這些多項(xiàng)式所定義集合中胞腔相鄰的信息.使用這些胞腔相鄰信息,多項(xiàng)式所定義集合能作為有限數(shù)目半代數(shù)連通分支不相交的并,而且這些連通分支能被刻畫.通過迭代,能獲得排列中所有的連通分支.而且算法7能在有限步內(nèi)結(jié)束.更多地,對(duì)空間中給定的一個(gè)點(diǎn),能夠判斷這個(gè)點(diǎn)是否包含于某個(gè)連通分支.這個(gè)方法能被應(yīng)用于碰撞檢測(cè),機(jī)器人學(xué)等領(lǐng)域.

4 結(jié)論

參考文獻(xiàn)

[1]Halperin D,Sharir M.Arrangements and Their Applications in Robotics:Recent Developments.In WAFR: Proceedings of the Workshop on Algorithmic Foundations of Robotics[M].Natick:Springer-Star,1995.

[2]Rimon E,Boyd S.Obstacle collision detection using best ellipsoid f i t[J].Journal of Intelligent and Robotic Systems,1997(2):105-126.

[3]Lin X,Ng T T.Contact detection algorithms for three-dimensional ellipsoids in discrete element method[J]. International Journal for Numerical and Analytical Methods in Geomechanics,1995,19(9):653-659.

[4]Perram J W,Rasmussen J,Praestgaard E,et al.Ellipsoid contact potential:Theory and relation to overlap potentials[J].Physical Review E,1996(6):6565-6572.

[5]Collins G E.Quantif i er elimination for real closed f i elds by cylindrical algebraic decomposition[J].Automata theory and formal languages,1975,33(6):134-183.

[6]Basu S,Pollack R,Roy M F.Algorithms in Real Algebraic Geometry[M].Berlin:Springer-Verlag,2003.

[7]Arnon D S,Collins G E,McCallum S.Cylindrical algebraic decomposition,II:An adjacency algorithm for the plane[J].SIAM J.Comput.,1984,13(4):878-889.

[8]Arnon D S,Collins G E,McCallum S.An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space[J].J.Symbolic Comput.,1988(5):163-187.

[9]Arnon D S.Algorithms for the Geometry of Semi-Algebraic Sets[M].Madison:Springer-Vienna,1981.

[10]Schwartz J,Sharir M.On the piano movers′problem II.General techniques for computing topological properties of real algebraic manifolds[J].Advances in Applied Mathematics,1983(4):298-351.

[11]Arnon D S,McCallum S.A polynomial-time algorithm for the topological type of a real algebraic curveextended abstract[J].Rocky Mountain J.Math.,1984(4):849-852.

[12]Arnon D S,Collins G E,McCallum S.Cylindrical algebraic decomposition,I:The basic algorithm[J].SIAM J.Comput.,1984,13(4):865-877.

[13]Chen Yufu.Lectures on Computer Algebra[M].Beijing:Higher education Press,2009.

Description of the connected components of arrangements

Gao Ben
(College of Mathematics,Taiyuan University of Technology,Taiyuan 030024,China)

We give an algorithm for computing connected components of arrangements of n compact semialgebraic sets inby using the methods of cylindrical algebraic decomposition and simplif i ed cell adjacencies.

connected component,compact semi-algebraic set,cylindrical algebraic decomposition, cell adjacency

O187.1

A

1008-5513(2014)02-0154-12

10.3969/j.issn.1008-5513.2014.02.006

2013-01-21.

山西省回國(guó)留學(xué)人員科研資助項(xiàng)目(2013-045);太原理工大學(xué)校青年項(xiàng)目基金(2013Z026).

高犇(1985-),博士,講師,研究方向：計(jì)算機(jī)代數(shù).

2010 MSC:08B8