Consistency checking for Euclidean spatial constraints: a dimension graph approach

Xuan Liu, Shashi Shekhar, Sanjay Chawla

Abstract

In this paper, we address the problem of consistency checking for Euclidean spatial constraints. A dimension graph representation is proposed to maintain the Euclidean spatial constraints among objects. The basic idea is to project the spatial constraints on both X and Y dimensions, and to construct a dimension graph on each dimension. Using a dimension graph representation transforms the problem of consistency checking into the problem of graph cycle detection. Consistency checking can be achieved with O(N+E) time as well as space complexity, where N is the number of spatial objects, and E is the number of spatial predicates in the constraint. The proposed approach is faster than O(N/sup 2/) when the number of predicates is much smaller than N/sup 2/ and there are few disjunctions in the spatial constraint. The dimension graph and consistency checking algorithm can be used for points, intervals and polygons in two-dimensional space. The algorithm can also guarantee global consistency.
BibTeX
@inproceedings{liu2000consistency,
  author = {Xuan Liu and Shashi Shekhar and Sanjay Chawla},
  title = {{Consistency checking for Euclidean spatial constraints: a dimension graph approach}},
  booktitle = {ICTAI},
  year = {2000},
  doi = {10.1109/tai.2000.889891},
}

Loading related content...

Figure