tween spatial objects. Implicit knowledge about spatial relations is then derived by constraint propagation5. Previous research has found that the mathematical notion of a *relation algebra* and related notions are well-suited for this kind of reasoning. In many cases, relation algebra-based reasoning only provides approximate results [26] and the constraint consistency problem for relative position calculi is NP-hard [27]. Hence we use constraint reasoning with polynomial time algorithms as an approximation of an intractable problem. The technical details of constraint reasoning are explained in Section 2.3.

In point-based reasoning, all objects are mapped onto the plane. The centers of projected objects can be used as point-like representation of the objects. By contrast, Schlieder's line segment calculus [24] uses more complex basic entities.

Thus, it is based on extended objects which are represented as oriented straight line segments (see Fig. 1). These more complex basic entities capture important features of natural objects:

## - Natural Objects Are Extended.

- Natural Objects often have an intrinsic direction.

![0_image_0.png](0_image_0.png)

Oriented straight line segments (which were called *dipoles* by Moratz et al. [28])
are the simplest geometric objects presenting these features. Dipoles may be specified by their start and end points.

Using dipoles as basic blocks, more complex objects can be constructed (e.g.

polylines, polygons) in a straightforward manner. Therefore, dipoles can be used as the basic units in numerous applications. To give an example, line segments are central to edge-based image segmentation and grouping in computer vision. In addition, GIS systems often have line segments as basic entities [29]. Polylines are particularly interesting for representing paths in cognitive robotics [30] and can serve as the geometric basis of a mobile robot when autonomously mapping its working environment [31].

The next sections of this paper present a detailed and technical description of dipole calculi. In Section 2 we introduce the relations of the dipole calculi 5For an application of constraint-based reasoning for spatial agents, we refer the reader to the AIBO robot example in [14]