Spatial reasoning with RCC 8 and connectedness constraints in Euclidean spaces
Spatial reasoning with RCC 8 and connectedness constraints in Euclidean spaces
复制标题
使用 RCC 8 进行空间推理和欧几里德空间中的连通性约束
DOI：
10.1016/j.artint.2014.07.012
复制
发表时间：
2014
影响因子：
14.4
通讯作者：
Kontchakov R
中科院分区：
文献类型：
--
作者：
Kontchakov R
RCC 8语言是一种被广泛研究的描述空间区域拓扑结构的形式主义。这种语言的变量范围在n维欧几里得空间的非空的、正则的闭集的集合上，这里表示为RC+（R n），它的非逻辑原语允许我们指定这些集合的内部、外部和边界如何相交。关键问题是可满足性问题：给定m个变量的原子RCC 8-约束的有限集合，确定是否存在满足它们的RC+（Rn）元素的m元组。已知这些问题对于所有n≥ 1都是一致的，因此RCC 8-可满足性与维数无关。这个常见的可满足性问题是NLogSpace-complete。不幸的是，RCC 8缺乏手段说，一个空间区域包括一个“单件”，本文调查会发生什么事时，这个设施被添加。我们考虑RCC 8的两个扩展：RCC 8 c，其中我们可以说一个区域是连通的，RCC 8 c，其中我们可以说一个区域有一个连通的内部。这两种语言的可满足性问题很容易看出取决于维数n，其中n≤ 3。此外，在RCC 8 c的情况下，我们表明，存在有限的约束集，满足RC+（R 2），但只有“野生”地区没有可能的物理意义。这促使我们考虑对非空、正则闭、多面体集的更具限制性的域RCP+（R n）的解释。我们证明了（a）RCC 8 c的可满足性问题（B）RC+（R2）和RCP+（R2）上的RCC 8 c的可满足性问题是相同的，是NP完全的;（3）RC+（R2）和RCP+（R2）上RCC 8 c的可满足性问题是不同的，而RCP+（R2）是NP完全的. RC+（R2）上RCC 8 c的可满足性问题的判定性是公开的.当n≥ 3时，RCC 8 c和RCC 8 c β与RCC 8没有显著差异.最后，我们回答以下问题：给定一组RCC 8 c-或RCC 8 c-约束在RC+（Rn）或RCP+（Rn）上可满足，最简单的满足分配有多复杂？特别是，我们展示了，对于这两种语言，一个序列的约束Φ n，满足RCP+（R 2），使Φ n的大小在n中多项式增长，而满足Φ n的多边形的最小配置切割平面成若干片，指数增长。我们进一步表明，在RC+（R 2）上，RCC 8 c再次需要指数级大的令人满意的图，而RCC 8 c可以迫使处于令人满意的配置的区域具有无限多个分量。
The language RCC 8 is a widely-studied formalism for describing topological arrangements of spatial regions. The variables of this language range over the collection of non-empty, regular closed sets of n-dimensional Euclidean space, here denoted RC+(R n), and its non-logical primitives allow us to specify how the interiors, exteriors and boundaries of these sets intersect. The key question is the satisfiability problem: given a finite set of atomic RCC 8-constraints in m variables, determine whether there exists an m-tuple of elements of RC+(R n) satisfying them. These problems are known to coincide for all n≥ 1, so that RCC 8-satisfiability is independent of dimension. This common satisfiability problem is NLogSpace-complete. Unfortunately, RCC 8 lacks the means to say that a spatial region comprises a ‘single piece’, and the present article investigates what happens when this facility is added. We consider two extensions of RCC 8: RCC 8 c, in which we can state that a region is connected, and RCC 8 c∘, in which we can instead state that a region has a connected interior. The satisfiability problems for both these languages are easily seen to depend on the dimension n, for n≤ 3. Furthermore, in the case of RCC 8 c∘, we show that there exist finite sets of constraints that are satisfiable over RC+(R 2), but only by ‘wild’regions having no possible physical meaning. This prompts us to consider interpretations over the more restrictive domain of non-empty, regular closed, polyhedral sets, RCP+(R n). We show that (a) the satisfiability problems for RCC 8 c (equivalently, RCC 8 c∘) over RC+(R) and RCP+(R) are distinct and both NP-complete;(b) the satisfiability problems for RCC 8 c over RC+(R 2) and RCP+(R 2) are identical and NP-complete;(c) the satisfiability problems for RCC 8 c∘ over RC+(R 2) and RCP+(R 2) are distinct, and the latter is NP-complete. Decidability of the satisfiability problem for RCC 8 c∘ over RC+(R 2) is open. For n≥ 3, RCC 8 c and RCC 8 c∘ are not interestingly different from RCC 8. We finish by answering the following question: given that a set of RCC 8 c-or RCC 8 c∘-constraints is satisfiable over RC+(R n) or RCP+(R n), how complex is the simplest satisfying assignment? In particular, we exhibit, for both languages, a sequence of constraints Φ n, satisfiable over RCP+(R 2), such that the size of Φ n grows polynomially in n, while the smallest configuration of polygons satisfying Φ n cuts the plane into a number of pieces that grows exponentially. We further show that, over RC+(R 2), RCC 8 c again requires exponentially large satisfying diagrams, while RCC 8 c∘ can force regions in satisfying configurations to have infinitely many components.