Realizing RCC8 networks using convex regions
  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.
