License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.COSIT.2017.4
URN: urn:nbn:de:0030-drops-77503
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7750/
Go to the corresponding LIPIcs Volume Portal

Karlsen, Leif Harald ; Giese, Martin

An Efficient Representation of General Qualitative Spatial Information Using Bintrees

pdf-format:
LIPIcs-COSIT-2017-4.pdf (0.5 MB)

Abstract

In this paper we extend previous work on using bintrees as an efficient representation for qualitative information about spatial objects. Our approach represents each spatial object as a bintree satisfying the exact same qualitative relationships to other bintree representations as the corresponding spatial objects. We prove that such correct bintrees always exists and that they can be constructed as a sum of local representations, allowing a practically efficient construction. Our representation is both efficient, w.r.t. storage space and query time, and can represent many well-known qualitative relations, such as the relations in the Region Connection Calculus and Allen's Interval Algebra.

BibTeX - Entry

@InProceedings{karlsen_et_al:LIPIcs:2017:7750,
  author =	{Leif Harald Karlsen and Martin Giese},
  title =	{{An Efficient Representation of General Qualitative Spatial Information Using Bintrees}},
  booktitle =	{13th International Conference on Spatial Information Theory (COSIT 2017)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-043-9},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{86},
  editor =	{Eliseo Clementini and Maureen Donnelly and May Yuan and Christian Kray and Paolo Fogliaroni and Andrea Ballatore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7750},
  URN =		{urn:nbn:de:0030-drops-77503},
  doi =		{10.4230/LIPIcs.COSIT.2017.4},
  annote =	{Keywords: Qualitative spatial data, Bintree, Data structure}
}

Keywords: Qualitative spatial data, Bintree, Data structure
Collection: 13th International Conference on Spatial Information Theory (COSIT 2017)
Issue Date: 2017
Date of publication: 29.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI