A ternary Relation Algebra of directed lines
  We define a ternary Relation Algebra (RA) of relative position relations on
two-dimensional directed lines (d-lines for short). A d-line has two degrees of
freedom (DFs): a rotational DF (RDF), and a translational DF (TDF). The
representation of the RDF of a d-line will be handled by an RA of 2D
orientations, CYC_t, known in the literature. A second algebra, TA_t, which
will handle the TDF of a d-line, will be defined. The two algebras, CYC_t and
TA_t, will constitute, respectively, the translational and the rotational
components of the RA, PA_t, of relative position relations on d-lines: the PA_t
atoms will consist of those pairs <t,r> of a TA_t atom and a CYC_t atom that
are compatible. We present in detail the RA PA_t, with its converse table, its
rotation table and its composition tables. We show that a (polynomial)
constraint propagation algorithm, known in the literature, is complete for a
subset of PA_t relations including almost all of the atomic relations. We will
discuss the application scope of the RA, which includes incidence geometry, GIS
(Geographic Information Systems), shape representation, localisation in
(multi-)robot navigation, and the representation of motion prepositions in NLP
(Natural Language Processing). We then compare the RA to existing ones, such as
an algebra for reasoning about rectangles parallel to the axes of an
(orthogonal) coordinate system, a ``spatial Odyssey'' of Allen's interval
algebra, and an algebra for reasoning about 2D segments.
