Abstract
The concrete problem this paper addresses is the following: Given a set of objects with a spatial interpretation and a set of qualitative relations, construct a bintree representation that returns the same answers to queries with the given relations over the spatial objects. We have previously constructed both theory [8] and an implementation [9] for constructing such qualitatively correct bintrees, with promising results. However, our previous work has been restricted to the construction of bintree-representations that are correct only w.r.t. part-of and overlaps relationships. In this paper we will extend the theoretical foundation to allow for representations that are correct with respect to a more expressive set of relations.