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

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