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. Using 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(n^5) 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.
Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.