Realizing RCC8 networks using convex regions
This work addresses the problem of representing qualitative spatial relations in high-dimensional conceptual spaces for AI and spatial reasoning, providing theoretical bounds that are incremental but specific to convex constraints.
The paper analyzes how restricting to convex regions affects the realizability of RCC8 networks, finding that consistent atomic networks can be convexly realized in 4D if 'partially overlaps' is disallowed, and in 3D if refinements of 'part of' are disallowed, with a general result for 2n+1 variables in n-dimensional space.
RCC8 is a popular fragment of the region connection calculus, in which qualitative spatial relations between regions, such as adjacency, overlap and parthood, can be expressed. While RCC8 is essentially dimensionless, most current applications are confined to reasoning about two-dimensional or three-dimensional physical space. In this paper, however, we are mainly interested in conceptual spaces, which typically are high-dimensional Euclidean spaces in which the meaning of natural language concepts can be represented using convex regions. The aim of this paper is to analyze how the restriction to convex regions constrains the realizability of networks of RCC8 relations. First, we identify all ways in which the set of RCC8 base relations can be restricted to guarantee that consistent networks can be convexly realized in respectively 1D, 2D, 3D, and 4D. Most surprisingly, we find that if the relation 'partially overlaps' is disallowed, all consistent atomic RCC8 networks can be convexly realized in 4D. If instead refinements of the relation 'part of' are disallowed, all consistent atomic RCC8 relations can be convexly realized in 3D. We furthermore show, among others, that any consistent RCC8 network with 2n+1 variables can be realized using convex regions in the n-dimensional Euclidean space.