A semi-dynamical approach for solving qualitative spatial constraint satisfaction problems

AbstractIn this paper, we solve the problem of determining a consistent instantiation of any finite, path-consistent and atomic network of RCC8 base relations. We already know that such networks that contain a finite number of variables have a realization in any dimension d≥1. The novelty of our work is that given any path-consistent and atomic constraint RCC8 network, we are able to construct in polynomial time a realization that satisfies it. For this purpose, we suitably instantiate the variables of such a network by associating to them some regular closed sets of the set of real numbers