(see Sect. 3.7). For analogous reasons, a derivation of DRAfp yields an oriented point calculus which explicitly contains the feature of parallelism, which is isomorphic to the *OPRA*∗
1 calculus[38]. This calculus DRAopp (opp stands for oriented points and parallelism) has the same base relations as DRAop with the exception of the relations RIGHTright, RIGHTleft, LEFTleft, and LEFTright.

The transformation from DRAfp to DRAopp is shown in Fig. 10.

Again, the mathematical properties of the oriented point calculus can be derived from the corresponding dipole calculus, see Corollary 55.

## 2.3 Relation Algebras For Spatial Reasoning

Standard methods developed for finite domains generally do not apply to constraint reasoning over infinite domains. The theory of relation algebras [39, 40]
allows for a purely symbolic treatment of constraint satisfaction problems involving relations over infinite domains. The corresponding constraint reasoning techniques were originally introduced for temporal reasoning [32] and later proved to be valuable for spatial reasoning [6, 19]. The central data for a calculus is given by:
- a list of (symbolic names for) *base relations*, which are interpreted as relations over some domain, having the crucial properties of *pairwise disjointness* and *joint exhaustiveness* (a general relation is then simply a set of base relations).

- a table for the computation of the *converses* of relations.

## - A Table For The Computation Of The Compositions Of Relations.

Then, the path consistency algorithm [41] and backtracking techniques [42] are the tools used to tackle the problem of consistency of constraint networks and related problems. These algorithms have been implemented in both generic reasoning tools GQR [43] and SparQ [44]. To integrate a new calculus into these tools, only a list of base relations and tables for compositions and converses really need to be provided. Thereby, the qualitative reasoning facilities of these tools become available for this calculus.10 Since the compositions and converses of general relations can be reduced to compositions and converses of base relations, these tables only need to be given for base relations. Based on these tables, the tools provide a means to approximate the consistency of constraint networks, list all their atomic refinements, and more.

Let b be the name of a base relation, and let Rb be its set-theoretic extension.

The converse (Rb)
` = {(x, y)|(*y, x*) ∈ Rb} is often itself a base relation and is denoted by b
`11. In the dipole calculus, it is obvious that the converse of a relation can easily be computed by exchanging the first two and second two 10With more information about a calculus, both of the tools can provide functionality that goes beyond simple qualitative reasoning for constraint calculi.

11In Freksa's double-cross calculus [2] the converses are not necessarily base-relations, but for the calculi that we investigate this property holds.