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  and an implementation  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.