Abstract: Region Connection Calculus（RCC） is a formal model for qualitative spatial representation and reasoning, such as RCC5, RCC8. Consistency problem of RCC8 is proved to be NP-hard. Fortunately, path-consistency can be used to decide the consistency of the tractable subsets of RCC8. However, the path-consistency algorithm with time and space complexity of [O(n3)] and [O(n2)] is still not practical for large and sparse constraint graphs. In order to use the divide and conquer strategy to accelerate the consistency checking, this paper proposes the concept of consistent cut, gives its definition as well as its necessary and sufficient condition. A series of cutting algorithms are also given to separate the constraint graph efficiently without changing the consistency. The experiments on the randomly generated constraint graph indicate the effectiveness of this method.

Key words: qualitative spatial reasoning, consistent cut, constraint satisfaction problem, path consistency algorithm, region connection calculus

摘要： 区域连接演算（Region Connection Calculus，RCC）是一种用于空间定性表示和推理的形式化模型，如RCC5，RCC8等，其一致性检查被证明是一个NP问题。幸运的是，在其可处理子集上，路径一致性和一致性等价，即便这样也有[O(n3)]的时间复杂度和[O(n2)]的空间复杂度。为了提高一致性检查的效率，提出了一致分割的概念，给出了其定义和成立的充分必要条件，用来将RCC8的约束图在保持一致性的前提下分割成若干个子图，分而求解各个子图的一致性；并随后给出了几种一致分割的充分条件，和相应的高效分割算法。在随机生成的大型、稀疏约束图上的实验表明了一致分割的有效性。

关键词: 空间定性推理, 一致分割, 约束满足问题, 路径一致性算法, 区域连接演算