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