RCC8的一致分割及其算法

崔文正

中國科學院 數學與系統科學研究院，北京 100190

1 引言

區域連接演算（Region Connection Calculus，RCC）是一種用來進行空間定性表示和推理的形式化模型[1]。而RCC8是區域連接演算中最常用的一個子集。RCC[1]最早由Randell等人于1992年基于Clarke利用二元連接關系公理化分體拓撲學（Mereotopology）的工作提出[2-3]，迄今20年取得了一系列重要的理論和應用成果，研究內容包括：RCC及其子集的推理可判定性[4-6]；基于認知的RCC評價[7-8]；RCC推理的復雜度[9-10]；拓撲復合表分析[11]和拓撲關系擴展[12-13]；集成多種空間、方向、時間、位置等信息的定性推理[14-17]等。

RCC8規定了兩個空間區域間可能的八種基本關系。這些關系是DC（相離）、EC（外切）、EQ（相等）、PO（部分重合），TPP（內切）和它的逆關系TPP-1，NTPP（真包含）和它的逆關系NTPP-1，圖1是這幾種關系的示意圖。這八種關系兩兩不相交，并且覆蓋了區域之間所有可能的關系，這種性質的關系被稱為JEPD（Jointly Exhaustive and Pairwise Disjoint）關系，或者基關系。因為空間中任何兩個區域的關系只可能是其中的一種，所以可以用基關系來表示兩個空間區域之間確定的知識，而不確定的知識則可以用可能的關系的析取來表示。

表1 RCC8復合運算表

圖1 RCC8示意圖

表1表示的是RCC8的基關系復合運算(·)表[18]，表中的項目是行與列中基關系的復合結果。如三個區域x、y、z，x和y關系為TPP，y和z的關系為EC，由表中TPP和EC的復合結果，可以得到x和z的關系可能是DC或者EC。*代表全關系，所有基關系的析取。

用約束來指定某兩個空間區域間為某個關系。RCC8的約束網絡由一個有限的空間區域集合和該集合上有限的約束集合構成[19]。如果兩個空間區域在約束網絡中沒有約束，那么就認為它們的約束是全關系。為了方便使用圖論的定理和結果，定義了一種圖結構來描述約束網絡，稱為約束圖（見2.1節）。

如果有r?R，稱關系r是R的細化（refinement）。如果約束圖G′與G有相同的頂點集合，且對于任兩個頂點在G′中的約束關系r和在G中的約束關系R，都有r?R，稱G′是G的一個細化[18]。

一個給定的約束圖G是一致的就意味著存在另一個約束圖G′是G的細化，并且G′中所有頂點之間的約束都是基關系。G′也被稱為G的一個一致解。一般求解約束圖的一致性是一個NP問題，要用回溯法求解，復雜度是指數級的。

路徑一致性是一致性的一個必要條件，它只要求約束圖中任何三個區域構成的約束圖都是一致的。路徑一致性算法的時間復雜度是O(n3)[10]，將路徑一致性算法的運行結果稱為路徑一致性解。RCC8可處理子集指的是可以在多項式時間內求解一致性的RCC8關系集合，如果將約束關系限制在RCC8的可處理子集、C8或Q8的話，路徑一致性和一致性等價[9]。

現有的定性空間推理機有GQR[20]、PelletSpatial[21]、PyRCC8-?[22]。首先利用路徑一致性算法對約束圖進行路徑一致性檢查，然后對路徑一致性解使用回溯法進行一致性判定。

對大型約束圖，求一致性解的回溯法代價太高，即便是路徑一致性算法，O(n3)的時間復雜度也是較高的。為了解決大型、稀疏的約束圖的一致性檢查問題，Huang證明了對于RCC8的可處理子集有Patchwork的性質[23]。Sioutis和Koubarakis利用Patchwork性質將約束圖三角化，以此提高路徑一致性推理效率[22]。Li和Huang等人討論了區間代數（IA）和RCC分解的方法[24-25]，但是這些工作只對關系全部為基關系的約束圖有效。

本文從圖論中的割和割集的概念出發，提出一致分割的概念。目標是在保持一致性的條件下，將一個約束圖G分割成若干個不相交的子圖，通過檢查規模較小的子圖的一致性來判斷G的一致性，以此降低一致性檢查時間。第2章介紹了約束圖、分割、Patchwork等的基礎知識，并基于此提出了一致分割的定義及其成立的充分必要條件。第3章給出了兩個一致分割的充分條件和基于這兩個充分條件的高效的一致分割算法。第4章采用隨機生成的大型稀疏約束圖進行實驗，驗證了一致分割算法的有效性。

2 一致分割

本章介紹文章的主要內容：約束圖的一致分割的定義和充分必要條件。這主要源自于圖論中的割的概念和RCC8的Patchwork[23]性質。

2.1 約束圖

可以用約束圖來表示RCC8的約束網絡。一般情況下，約束圖應該是一個有向圖。頂點v代表空間區域，而v1，v2之間的有向邊則代表v1，v2的約束。但如果經過一步預處理，也可以使用無向圖來表示約束網絡。

對任一個約束網絡都可以做如下預處理。假設約束網絡中vi，vj的約束為R，vj，vi的約束為Q：若Q和R不互逆，則將vi，vj的約束賦為R∩Q-1，vj，vi的約束賦為Q∩R-1，這樣使vi，vj和vj，vi的約束互逆；若Q=R=*（全關系），則刪除vi，vj和vj，vi的約束。顯然，經過預處理的約束網絡仍與原約束網絡等價。經過預處理就可以用無向圖來描述約束網絡。

定義1（約束圖）約束圖G=(V，E)是一個無向圖，V，E分別是圖的頂點集和邊集，有V={vi|0≤i≤n}，E={(vi，vj，R)|0≤i＜j≤n，(vi，vj)∈R，(vj，vi)∈R-1} 。約束圖中沒有邊連接的頂點對(vi，vj)表示有約束(vi，vj)∈*成立，*為全關系。

定義2（分割和割集）約束圖G=(V，E)的分割S=(G1，G2)，其中Gk=(Vk，Ek)，V1∩V2= ? ，Ek={(vi，vj，R)∈E|vi，vj∈Vk} ，k=1，2 。 割 集Scut={(u，v，R)∈E|u∈G1，v∈G2}。

定義3（橋）橋是割集元素數為1的分割。

定義4（誘導子圖）對于約束圖G=(V，E)和其子圖H=(V1，E1)，如果V1?V，有E1={(vi，vj，R)∈E|vi，vj∈V1}，那么稱H為G的誘導子圖，記為H=GV1。

值得注意的是誘導子圖的這個表示方法將在與Patchwork相關的工作中被頻繁用到，它代表的含義就是由圖G中一部分頂點和這些頂點在G所有邊構成的子圖。另外，VG代表圖G的頂點集合。

2.2 Patchwork

Patchwork性質：如果兩個一致的約束圖的一致解在共有的頂點上的約束是相同的，那么這兩個約束圖的并依然是一致的[23]，如定義5所描述。

RCC8一致性檢查是一種約束滿足問題，而且基于RCC8的可處理子集8，C8，Q8的一致性問題是有Patchwork性質的[23]。在下文中如無特殊說明，討論范圍都限定于RCC8可處理子集。

2.3 一致分割及其成立條件

為了描述這種保持一致性的分割，給出一致分割的定義：

定義6（一致分割）一個約束圖G的分割是一個一致分割，當且僅當分割成的兩個子約束圖G1，G2的一致性與G的一致性等價。

可以知道G如果是一致的，那么必然存在一個解S，可知分別是G1，G2的解。所以容易推出一致分割的等價描述。

推論1對于一個分割，如果分割的兩個子約束圖G1，G2是一致的則G也是一致的，那么這個分割是一個一致分割。

由于在可處理子集中，約束圖的路徑一致性和一致性是等價的，可以結合RCC8可處理子集的Patchwork性質得到一致分割的充分必要條件：

定理1 約束圖G=(V，E)的分割S={G1，G2}，割集為Scut，記。S是一致分割的充分必要條件是：Gs，G1，G2都是路徑一致的且對于Gs，G1，G2的路徑一致性 解Gs*，G1*，G2*有。

由于Gs*，G1*，G2*是Gs，G1，G2路徑一致性解，那么G1∪G2∪Gs滿足一致性，則G一致性得證。則由推論1知S為一致分割。

推論2約束圖G如果含有若干個連通分量，那么所有連通分量的一致性和G的一致性等價。

這個推論的另一個等價描述是：

推論3如果約束圖的割集為空集，這個分割是一致分割。

3 一致分割算法

從上文可知，如果割集中所有頂點的誘導子圖的路徑一致性解和其他兩個分割后的子圖的解滿足定理1的條件，就可以得到約束圖的一致性。

本章主要討論這個定理的應用方法。3.1節給出了尋找一致分割的算法，并分析此算法的性能。為了提高約束圖一致分割的效率，3.2節給出了兩種一致分割的充分條件，和相應的高效分割算法。

3.1 一致分割尋找算法

一般的，可以通過檢查約束圖的所有分割，利用定理1篩選出該約束圖的所有一致分割。

一致分割尋找算法：

輸入：約束圖G

返回：一致分割集合Pc

1.P←{pi|pi為G的一個分割}

2.Pc←?

3.當P不是空集時：

4. 從P中選取分割pi，并將其從P中刪除

5. 利用定理1檢查pi是不是一致分割

6.pi是一致分割：將pi加入Pc

7.返回Pc

從定理1的特點和這個算法的過程可以看出直接使用這個一致分割尋找算法有以下兩個問題：

（1）一個圖的分割個數至少是(2n-1-1)個，所以這個算法至少也是指數級的。顯然這并不是一個實用的算法。

（2）充分必要條件不僅要求出分割的兩個子圖的路徑一致性解，也要求出割集相關的頂點在G里的誘導子圖H的路徑一致性解。如果求解H消耗的時間超過了分別進行一致性求解節約的時間，一致分割就無法減少總時間消耗了。

3.2 一致分割成立的充分條件

這一節給出充分條件來尋找一致分割。這些條件的缺點是不能如一致分割尋找算法找出任何一個圖所有的一致分割，但是對某些圖它們能高效地找到某些特殊的一致分割。在處理稀疏圖或者滿足一些特定結構的圖的時候，這些條件和其相對應的算法就非常有用。

3.2.1 橋分割

對于割集為橋的分割，有著如下定理所述的性質：

定理2約束圖中如果存在著橋，那么以這個橋作為割集的分割是一個一致分割。

這個結論可以使用Tarjan在1974年提出的Bridge-Finding算法[26]，在O(|E|+|V|)的時間內找出所有的橋，將這些橋從約束圖G中去除后所有連通分量的一致性和G的一致性是等價的，得到所有連通分量的算法時間復雜度也是O(|E|+|V|)。這樣完成一次約束圖關于橋的一致分割的時間復雜度也為O(|E|+|V|)。

3.2.2 弱關系分割

先給出弱關系的定義：

定義7（弱關系）RCC8中，如果存在一個基關系r滿足如下條件，就定義這個r為一個弱關系：

（1）r=r-1；

（2）?R，r?R·r；

（3）?R，r?r·R；

（4）r·r=*。

注：其中R代表任意一個RCC8關系，*代表全關系。

定理3約束圖的割集Gs所有約束中出現的關系集合記為RS，r為RCC8中的某個弱關系。如果?R∈RS，r?R，那么這個分割是一個一致分割。

證明G1，G2都滿足一致性，則一定存在一致解G1*，G2*，每個空間之間的關系都是基關系，那么需要證明G是一致的。有?R∈RS:r?R成立，那么RS′是RS的一個細化，其中RS′所有的約束關系都可以細化為r（因為每個關系都包含r）。證明G*=G1*∪G2*∪Gs*是一個G的一致解。

因為G*只是由基關系構成的約束集合，那么可以用檢查路徑一致性確定G*是否一致?？梢匀稳∪ca，b和c∈，列舉所有可能的路徑。

（1）?i=1，2:a，b，c∈：三者之間的約束同在Gi*，由Gi*一致性易知路徑一致。

（2）三個空間不同在一個空間集合，不失一般性假設：a∈，b∈，c∈?？梢灾繰ac，Rbc∈RS′，那么由r=r-1知道Rac=Rbc=Rca=Rcb=r，且有?R，r?R·r，r?r·R，r·r=R*。所以可以知道Rab無論為哪個基關系，都不會給這三個點構成的任何一條路徑帶來不一致。由于選取三個點的一般性得知G*是一致的。

由于G*是G的細化，且G*中約束都為基關系，可知G*是G的一個一致解，G的一致性得證。由推論1知滿足定理3性質的分割為一致分割。

注意，在定理3的證明中并沒有用到可處理子集的性質，說明定理3對于所有的RCC8約束圖都成立。

可以從復合運算表中驗證DC、PO都是弱關系。所以割集中的關系如果全都包含DC或者全都包含PO的話，這個分割就是一個一致分割。利用弱關系進行判斷和分割的算法如下所示，其中遍歷算法采用廣度優先搜索（BFS）或者深度優先搜索（DFS）皆可，本文以深度優先搜索為例。

弱關系分割：

深度優先搜索（DFS）：

如上所示，分割算法與經典的深度優先搜索算法唯一的不同之處在于增加了第15行的判斷：弱關系分割算法將約束關系包含r的邊視為不連通。這樣使得SG中不同的分割子圖之間只有兩種可能，要么沒有邊相連，要么連接兩個子圖的邊的約束關系都包含r，根據定理3這個算法的正確性得證。

另外，由于增加的第15行只有O()1的復雜度，所以這個算法仍然和深度優先搜索算法有著相同的復雜度。根據深度優先搜索的相關結論[27]，可以得出弱關系分割算法復雜度也僅為O(|E|+|V|)。

3.2.3 橋分割和弱關系分割的關系

以上證明了兩種一致分割的充分條件，可以看出，這兩個條件是互相獨立的。在一個約束圖里面，可以采用幾種不同的分割條件去判斷約束圖是否是可分割的。

圖2給出了一種使用多種分割條件將約束圖分割至不能分割為止的流程。該方法先后使用不同的一致分割算法嘗試對約束圖進行分割，直到分割結果不再滿足任何一個一致分割條件。

圖2 多分割條件一致分割流程圖

值得注意的是圖2中三種一致分割算法的調用順序不會改變最終分割結果。因為三種算法都是將滿足某種條件的割集從約束圖G中刪除，而后將各個連通分量作為分割結果。假設調用一致分割條件順序為A1→A2→…→An。如果Si是G滿足一致分割條件Ai的割集，使用A1，A2，…，Ai-1條件進行分割的話有兩種可能：（1）Si中的一部分邊被A1，A2，…，Ai-1條件刪除，剩下的邊構成集合S′i依然是滿足一致分割條件的割集；（2）A1，A2，…，Ai-1條件不會刪除Si中的邊。顯然，無論是哪一種情況這個一致分割條件Ai的分割效果都不會被影響。

然而，三種算法的調用順序對于運行時間會有一定的影響。比如對于圖3，如果按照圖2中的調用順序進行分割的話，將進行4次迭代才能將約束圖分割到不再可分。而采用DC子圖分割→ PO子圖分割→橋分割這樣的順序，就只用迭代兩次。

從三種分割的算法可以看出，約束圖G不能用同一個分割條件連續分割兩次?；谶@個特點可以得到：

圖3 分割條件調用順序差異帶來運行時間差異示例

定理4對于約束圖G，利用多分割條件一致分割時，若調用分割條件順序為A1→A2→A3時，若G在某一次迭代中可以被Am分割，且不能被所有Ai(i＞m)分割，那么下一次迭代只可能：

（1）G不能用任何條件分割；

（2）存在某個條件Aj(j＜m)可以將其分割。

證明情況1，算法此時達到迭代終止條件。

情況2，首先一定存在一個條件可以分割G，否則就落到情況1中。不妨設第一個可以用來分割G的條件為Ak，首先k=m不可能成立，因為上一輪迭代中G被Am分割，其子圖不能被Am繼續分割；其次m＜k≤3也不能成立，這又與上一輪迭代中G不能被所有Ai(i＞m)分割相矛盾。所以必存在某個條件Aj(j＜m)可以將其分割。

從圖2中可以看出每次迭代的時間消耗是一定的，所以迭代次數越少，整個算法時間消耗就越小。

可以看出，降低迭代次數的關鍵在于增加每次迭代中成功分割的次數。

表2就是最壞情況的迭代示例。調用順序為A1→A2→A3，且在Ai+1的分割成功之后才能使用Ai分割成功。表格中的行代表分割條件，列代表迭代輪次，其中的成功代表該輪次用對應分割條件分割成功，如果某輪次中所有條件都未被成功調用就代表該約束圖已經無法再進行分割?？梢钥闯?，平均每次迭代成功分割次數約為1.5次。

表2 最不利的迭代示例

而如果將調用的順序改為A3→A2→A1，如表3所示，之后的分割條件正好可以用上之前的分割結果，這樣平均每次迭代成功分割次數約為3次。由于成功分割順序是一樣的，兩次成功分割總次數相同，那么分割時間之比為2。每一次迭代的復雜度是O(|E|+|V|)，則最有利和最不利的總時間只差O(|E|+|V|)，可知調用順序對算法的效率沒有很大的影響。

表3 最有利的迭代示例

4 實驗

本章設計并進行實驗，用來驗證以上提出的分割算法對于大型稀疏空間約束圖一致性檢查確實能夠起到提高效率的作用。

4.1 實驗設計

在實驗中用約束圖的邊數(E)和頂點個數(V)之商D=E/V的值來度量圖的稀疏程度，D稱為平均度。分別在D=0.5，1，2，3時，觀察約束圖的路徑一致性檢查時間和約束圖頂點個數的關系。約束圖是隨機生成的：限定約束圖的頂點個數為V(10 000～60 000)，在所有頂點對的集合中隨機取出E=V·D個項用邊相連，并從8中隨機選取關系作為邊的約束。

實驗環境是：Intel Core i7-2600 CPU 3.40 GHz 8核，內存20 GB，操作系統Fedora 15 64 bit，GCC 4.5.4；推理機采用GQR-1418[20]（同樣也可以采用其他的推理機進行實驗）。

4.2 實驗結果

圖4～圖7分別表示在不同的平均度下，約束圖的路徑一致性算法運行時間和約束圖頂點個數關系。其中灰柱代表直接用推理機對約束圖進行路徑一致性檢查所用的時間，黑柱代表先利用一致分割進行預處理后，推理機進行路徑一致性檢查所用時間。沒有立柱代表推理機無法處理這個量級的約束圖。

從圖4和圖5中可以看出，在E/V≤1，即約束圖十分稀疏的時候，直接使用推理機是非常耗時而低效的；而且當頂點個數多于一定量的時候（50 000），由于內存限制，推理機不能夠繼續進行。但是如果先進行分割的話，不僅在很高的頂點個數時也能夠正常運行，而且運行時間也能一直維持在很低的水平上。

可以看出，隨著E/V值的增大，分割后的路徑一致性檢查運行時間越來越接近直接進行路徑一致性檢查的時間。在E/V=2時，分割算法依然有很高的效率提高作用，并且能完成直接檢查路徑一致性不能完成的任務；但是在E/V=3時候，分割算法已經不能解決直接檢查無法處理的約束圖了，不過此時分割算法還是能夠帶來可觀的效率提高。

圖4 E/V=0.5時路徑一致性檢查時間和約束圖頂點數關系

圖5 E/V=1時路徑一致性檢查時間和約束圖頂點數關系

圖6 E/V=2時路徑一致性檢查時間和約束圖頂點數關系

圖7 E/V=3時路徑一致性檢查時間和約束圖頂點數關系

從實驗結果可以看出兩點：對大型的稀疏約束圖來說，先進行一致分割所帶來的效率提高是非常大的，這說明本文提出的算法是有效的；隨著約束圖的密度上升分割算法帶來的效率提高會越來越小，這是由于一般情況下，越稠密的圖分割會越困難，這也表明了本文方法的局限性。

5 結論和工作展望

5.1 結論

本文給出了一致分割的概念，將空間約束圖的一致性檢查轉化為其一致分割子圖的一致性檢查。

一致分割可以作為RCC約束圖的一致性檢查推理機[2-4]的預處理過程。對于大型的、稀疏的RCC8約束圖一致性檢查，可以采用一致分割算法先對約束圖進行分割，然后分而檢查子圖的一致性。本文方法具有以下幾個優勢：

（1）一致分割算法時間復雜度為O(|E|+|V|)，遠低于路徑一致性算法復雜度O(n3)。即便面對大型的約束圖，也可以用很小的時間代價去檢驗這個圖是否可以分割。

（2）實驗過程表明面對稀疏的約束圖，如果預先進行一致分割處理，能夠大幅度減少總的時間消耗。

（3）對于一些由于內存限制推理機無法處理的大型稀疏約束圖，一致分割算法能夠將其分割成為若干對推理機來說可處理的子圖，使得一致性檢查成為可能。

一致分割算法的弱點在于不能夠對于所有的約束圖都起作用。對于不符合一致分割充分條件的約束圖，算法就無法為推理機提高效率了。

5.2 工作展望

一致分割算法還有著很多有待深入思考的問題。首先是一致分割算法在真實數據中的效果。本文的實驗數據是隨機生成的約束圖，對于真實數據是否仍有類似的結論是下一步要討論的問題。例如RCC可以被用于地理信息的定性描述[28]。地理信息常常有著很強的層次結構，比如洲、國家、省、市、縣等，由于高層級的區域之間（比如洲）的約束偏少，這也使得將描述地理信息的約束圖一致分割成為可能。

其次，可以將分割后各個子圖的一致性檢查過程并行化，因為這些過程是互相獨立的，所以并行運算可以進一步地提高一致性檢查的效率。

另外，一致分割也可以用來確定約束圖出現不一致的位置。若要找哪些區域之間的約束引入了不一致性，只需要檢查具有不一致性的分割子圖中區域之間的關系，而不需要去分析一致的子圖。

最后，尋找更多的一致分割條件和算法，對其他的基于JEPD關系的推理演算進行一致分割的探索也都是未來研究的方向。

[1]Randell D A，Cui Zhan，Cohn A G.A spatial logic based on regions and connection[C]//Proceedings of the 3rd Inter-national Conference on Knowledge Representation and Reasoning.San Mateo，USA：Morgan Kaufmann，1992：165-176.

[2]Clarke B L.A calculus of individuals based on connection[J].Notre Dame Journal of Formal Logic，1981，22（3）：204-218.

[3]Clarke B L.Individuals and points[J].Notre Dame Journal of Formal Logic，1985，26（1）：61-75.

[4]Dornheim C.Undecidability of plane polygonal mereotopology[C]//Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning.[S.l.]：Morgan Kaufman，1998：342-353.

[5]Gotts N M.Using the RCC formalism to describe the topology of spherical regions，Technical Report 96.24[R].School of Computer Studies，University of Leeds，1996.

[6]Bennett B.Spatial reasoning with propositional logic[C]//Proceedings of the 4th International Conference on Knowledge Representation and Reasoning，1994：51-62.

[7]Knauff M，Rauh R，Renz J.A cognitive assessment of topological spatial relations：results from an empirical investigation[C]//Proceedings of the 3rd International Conference on Spatial Information Theory.Berlin：Springer，1997，1329：193-206.

[8]Renz J，Rauh R，Knauff M.Towards cognitive adequacy of topological spatial relations[C]//Proceedings of Spatial Cognition II.Berlin：Springer，2000，1849：184-197.

[9]Renz J.Maximal tractable fragments of the region connection calculus：a complete analysis[C]//Proceedings of the 16th International Joint Conference on Artificial Intelligence，Stocholm，Sweden.San Francisco，California，USA：Morgan Kaufmann Publisher Inc，1999：448-454.

[10]Renz J，Nebel B.Efficient methods for qualitative spatial reasoning[J].Journal of Artificial Intelligence Research，2001，15：289-318.

[11]Li Sanjiang，Ying Mingsheng.Region connection calculus：its models and composition table[J].Artificial Intelligence，2003，145（1/2）：121-146.

[12]Cohn A G，Bennett B，Gooday J，et al.Qualitative spatial representation and reasoning with the region connection calculus[J].GeoInformatica，1997（1）：1-44.

[13]歐陽繼紅，富倩，劉大有.簡單凹形區域間空間關系的一種表示及推理模型[J].電子學報，2009，37（8）：1830-1836.

[14]王生生，劉大有，謝琦.集成多方面信息的定性空間推理及應用[J].軟件學報，2003，14（11）：1857-1862.

[15]陳娟，劉大有，賈海洋，等.基于MBR的拓撲、方位、尺寸結合的定性空間推理[J].計算機研究與發展，2010，47（3）：426-433.

[16]Li Sanjiang.Combining topological and directional information for spatial reasoning[C]//Proceedings of the 20th International Joint Conference on Artificial Intelligence（IJCAI-07），2007：435-440.

[17]Liu Weiming，Li Sanjiang，Renz J.Combining RCC-8 with qualitative direction calculi：algorithms and complexity[C]//Proceedings of the 21st International Joint Conference on Artificial Intelligence（IJCAI-09），2009：854-859.

[18]Renz J.Qualitative spatial reasoning with topological Information[M].Berlin，Heidelberg：Springer-Verlag，2002.

[19]Bodirsky M，W?lfl S.RCC8 is polynomial on networks of bounded treewidth[C]//Proceedings of the 22nd International Joint Conference on Artificial Intelligence，2011：756-761.

[20]Gantner Z，Westphal M，W?lfl S.GQR—a fast reasoner for binary qualitative constraint calculation[C]//AAAI Workshop on Spatial and Temporal Reasoning，2008.

[21]Stocker M，Sirin E.PelletSpatial：a hybrid RCC-8 and RDF/OWL reasoning and query engine[C]//Proceedings of the 6th International Workshop on OWL：Experiences and Directions，Virginia，USA，2009.

[22]Sioutis M,Koubarakis M.Consistency of chordal RCC-8 networks[C]//Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence，Athens，Greece，2012.

[23]Huang Jinbo.Compactness and its implications for qualitative spatial and temporal reasoning[C]//Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning，Rome，Italy，2012.

[24]Li Jason Jingshi，Huang Jinbo，Renz J.A divide-and-conquer approach for solving interval algebra networks[C]//Proceedings on 21st International Joint Conference on Artificial Intelligence，Pasadena，USA，2009：572-577.

[25]Huang Jinbo，Li Jason Jingshi，Renz J.Decomposition and tractability in qualitative spatial and temporal reasoning[J].Artificial Intelligence，2013，195：140-164.

[26]Tarjan R.A note on finding the bridges of a graph[J].Information Processing Letters，1974，2（6）：160-161.

[27]Cormen T H，Leiserson C E，Rivest R L，et al.Introduction to algorithms[M].[S.l.]：MIT Press，2001.

[28]Bennett B.The application of qualitative spatial reasoning to GIS[C]//Proceedings of the 1st International Conference on GeoComputation，1996：44-47.