HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2510
Title: Algorithms for hierarchical spatial reasoning
Authors: Papadias, Dimitris
Egenhofer, Max J.
Keywords: Spatial reasoning
Geographic databases
Direction relations
Path consistency
Issue Date: 1997
Citation: Geoinformatica vol. 1, no. 3 (Oct 1997), p.251-273.
Abstract: In several applications, there is the need to reason about spatial relations using multiple local frames of reference that are organized hierarchically. This paper focuses on hierarchical reasoning about direction relations, a special class of spatial relations that describe order in space (e.g., north or northeast). We assume a spatial database of points and regions. Points belong to regions, which may recursively be parts of larger regions. The direction relations between points in the same region are explicitly represented (and not calculated from coordinates). Inference mechanisms are applied to extract direction relations between points located in different regions and to detect inconsistencies. We study two complementary types of inference. The first one derives the direction relation between points from the relations of their ancestor regions. The second type derives the relation through chains of common points using path consistency. We present algorithms for both types of inference and discuss their computational complexity.
Rights: The original publication is available at http://www.springerlink.com/; DOI: 10.1023/A:1009760430440
URI: http://hdl.handle.net/1783.1/2510
Appears in Collections:CSE Preprints

Files in This Item:

File Description SizeFormat
dp1996a.pdf216KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.