Convex solutions of RCC8 networks

IOS Press
Publication Type:
Conference Proceeding
Proceedings of the 20th European conference on artificial intelligence (ECAI-2012), 2012, pp. 726 - 731
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2011006783OK_Schockaert.pdf1.4 MB
Adobe PDF
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.
Please use this identifier to cite or link to this item: