Abstract
We construct an homogeneous (and ?-categorical) representation of the relation algebra RCC8, which is one of the fundamental formalisms for spatial reasoning. As a consequence we obtain that the network consistency problem for RCC8 can be solved in polynomial time for networks of bounded treewidth. Qualitative spatial reasoning (QSR) is concerned with representation formalisms that are considered close to conceptual schemata used by humans for reasoning about their physical environment—in particular, about processes or events and about the spatial environment in which they are situated. The approach in qualitative reasoning is to develop relational schemas that abstract from concrete metrical data of entities (for example, time points, coordinate positions, distances) by subsuming similar (geo-) metric or topological con?gurations of entities into one qualitative representation. RCC8 [Randell et al., 1992b; Cohn and Hazarika, 2001] is a prominent relation algebra studied in QSR that deals with extended regions. The relation algebra is derived from a multi-sorted ?rst-order theory called region connection calculus. Its network consistency problem is one of the most fundamental tasks in qualitative spatial reasoning [Renz, 2002; Renz and Nebel, 2007; Bennett, 1998]. There have been numerous papers on the network consistency problem for RCC8, in particular about its mathematical foundations [Renz and Ligozat, 2005; Li and Ying, 2003], its computational complexity [Renz, 2002; Renz and Nebel, 2007; Bennett,