Qualitative spatial reasoning: A new approach to cyclic ordering of 2D orientations

;

URL
Dokumentart: Report (Bericht)
Schriftenreihe: Berichte des Fachbereichs Informatik der Universität Hamburg
Bandnummer: 223
Sprache: Englisch
Erstellungsjahr: 2000
Publikationsdatum:
SWD-Schlagwörter: Räumliches Schließen
Freie Schlagwörter (Englisch): Qualitative spatial reasoning , QSR
DDC-Sachgruppe: Informatik
BK - Klassifikation: 54.72

Kurzfassung auf Englisch:

We propose a new approach to cyclic ordering of 2D orientations, consisting of a relation algebra (RA) whose universe is a set of ternary relations. An atom of the RA expresses for triples $(z_1,z_2,z_3)$ of orientations whether each of the three orientations is equal to, to the left of, opposite to, or to the right of each of the other two orientations. The RA has $24$ atoms and the elements of its universe consist of all possible $2^{24}$ subsets of the set of all atoms. Because we are dealing with ternary relations, we add {\em rotation} as an operation in addition to those present in Tarski's formalisation of RAs. Amongst other results, (1) we provide for the RA a constraint propagation procedure computing the closure of a problem under the different operations, which we show is polynomial, and complete for a subset including all atoms; (2) we prove that another subset, expressing only information on parallel orientations, is NP-complete; (3) we show that provided that a subset ${\cal S}$ of the RA includes two specific elements, deciding consistency for a problem expressed in the closure of ${\cal S}$ can be polynomially reduced to deciding consistency for a problem expressed in ${\cal S}$; and (4) we derive from the previous result that we “jump” from tractability to intractability if we add the universal relation to the set of all atoms of the RA. A comparison to the most closely related work in the literature indicates that the approach is promising.

Hinweis zum Urherberrecht

Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:

Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.

Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.