Convex Solutions of RCC8 Networks
Convex Solutions of RCC8 Networks
复制标题
RCC8网络的凸解
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Sanjiang Li
中科院分区：
文献类型：
--
作者：
Steven Schockaert;Sanjiang Li
RCC8是应用最广泛的定性空间推理演算之一。尽管已经探索了许多应用，其中RCC8关系指的是二维或三维空间中的地理或物理区域，但它们在概念推理中的应用仍处于相当初级的阶段。使用RCC8对概念空间进行推理的一个核心障碍是，在这种情况下，区域必须是凸的。本文研究了后一种需求如何影响RCC8网络的可实现性。具体来说，我们证明了2n + 1个变量上的一致RCC8网络在n维或更高的欧几里得空间中保证具有凸解。进一步证明了我们的界对于二维和三维空间是最优的，并且对于任意n≥4维，存在一个超过3n个变量的RCC8关系网络，该网络是一致的，但在n维欧几里德空间中不允许有凸解。
RCC8 is one of the most widely used calculi for qualitative spatial reasoning. Although many applications have been explored where RCC8 relations refer to geographical or physical regions in two- or three-dimensional spaces, their use for conceptual reasoning is still at a rather preliminary stage. One of the core obstacles with using RCC8 to reason about conceptual spaces is that regions are required to be convex in this context. We investigate in this paper how the latter requirement impacts the realizability of RCC8 networks. Specifically, we show that consistent RCC8 networks over 2n + 1 variables are guaranteed to have a convex solution in Euclidean spaces of n dimensions and higher. We furthermore prove that our bound is optimal for 2- and 3-dimensional spaces, and that for any number of dimensions n ≥ 4, there exists a network of RCC8 relations over 3n variables which is consistent, but does not allow a convex solution in the n-dimensional Euclidean space.
2D 和 3D 欧几里德空间中连通性约束的可判定性
DOI：
10.48550/arxiv.1104.0219
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Kontchakov R
通讯作者：
Kontchakov R