Name
Abstract | ||
|---|---|---|
We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a coordinate 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.artint.2004.10.010 | Artif. Intell. |
Keywords | Field | DocType |
co-ordinate system,basic model,cardinal direction,qualitative spatial reasoning,cardinal direction constraint,consistency checking,consistency checking problem,computational complexity,formal model | Discrete mathematics,Causal consistency,Local consistency,Sequential consistency,Correctness,Cardinal direction,Weak consistency,Consistency model,Equiconsistency,Mathematics | Journal |
Volume | Issue | ISSN |
163 | 1 | 0004-3702 |
Citations | PageRank | References |
35 | 1.23 | 30 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Spiros Skiadopoulos | 1 | 1139 | 65.60 |
| Manolis Koubarakis | 2 | 2790 | 322.32 |