Qualitative Spatial Logics for Buffered Geometries

Du, Heshan; Alechina, Natasha

Abstract

This paper describes a series of new qualitative spatial logics for checking consistency of sameAs and partOf matches between spatial objects from different geospatial datasets, especially from crowd-sourced datasets. Since geometries in crowd-sourced data are usually not very accurate or precise, we buffer geometries by a margin of error or a level of tolerance a E R≥0, and define spatial relations for buffered geometries. The spatial logics formalize the notions of 'buffered equal' (intuitively corresponding to `possibly sameAs'), 'buffered part of' ('possibly partOf'), 'near' (`possibly connected') and 'far' ('definitely disconnected'). A sound and complete axiomatisation of each logic is provided with respect to models based on metric spaces. For each of the logics, the satisfiability problem is shown to be NP-complete. Finally, we briefly describe how the logics are used in a system for generating and debugging matches between spatial objects, and report positive experimental evaluation results for the system.

Citation

Du, H., & Alechina, N. (in press). Qualitative Spatial Logics for Buffered Geometries. Journal of Artificial Intelligence Research, 56, 693-745. https://doi.org/10.1613/jair.5140

• Journal Article Type: Article
• Acceptance Date: Jul 18, 2016
• Online Publication Date: Aug 31, 2016
• Deposit Date: Jul 26, 2016
• Publicly Available Date: Aug 31, 2016
• Journal: Journal of Artificial Intelligence Research
• Print ISSN: 1076-9757
• Electronic ISSN: 1076-9757
• Publisher: AI Access Foundation
• Peer Reviewed: Peer Reviewed
• Volume: 56
• Pages: 693-745
• DOI: https://doi.org/10.1613/jair.5140
• Keywords: Artificial Intelligence
• Public URL: https://nottingham-repository.worktribe.com/output/800557
• Publisher URL: http://jair.org/papers/paper5140.html
• Related Public URLs: http://www.aaai.org/home.html