2026-07-22T06:32:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7750 2024-03-06T10:41:12Z ddc:004 open_access

An Efficient Representation of General Qualitative Spatial Information Using Bintrees Karlsen, Leif Harald Giese, Martin Qualitative spatial data Bintree Data structure 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leif Harald Karlsen and Martin Giese 2017 Is Part Of LIPIcs, Volume 86, 13th International Conference on Spatial Information Theory (COSIT 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.COSIT.2017.4 urn:nbn:de:0030-drops-77503 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2017.4 eng https://creativecommons.org/licenses/by/3.0/legalcode