首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On the consistency of cardinal direction constraints
Authors:Spiros Skiadopoulos  Manolis Koubarakis
Institution:a Knowledge and Database Systems Laboratory, School of Electrical and Computer Engineering, National Technical University of Athens, Zographou, 157 73 Athens, Greece
b Intelligent Systems Laboratory, Department of Electronic and Computer Engineering, Technical University of Crete, Chania, 731 00 Crete, Greece
Abstract:We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n5) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.
Keywords:Cardinal direction relations  Spatial constraints  Consistency checking  Qualitative spatial reasoning
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号