## On consistency checking of spatial relationships in content-based image database systems.(English)Zbl 1110.68377

Summary: We investigate the consistency problem for spatial relationships in content-based image database systems. We use the mathematically simple matrix representation approach to present an efficient (i.e., polynomial-time) algorithm for consistency checking of spatial relationships in an image.
It is shown that, there exists an efficient algorithm to detect whether, given a set SR of absolute spatial relationships, the maximal set of SR under $${\mathcal R}$$ contains one pair of contradictory spatial relationships. The time required by it is at most a constant multiple of the time to compute the transitive reduction of a graph or to compute the transitive closure of a graph or to perform Boolean matrix multiplication, and thus is always bounded by time complexity $$O(n^3)$$ (and space complexity $$O(n^2))$$, where $$n$$ is the number of all involved objects. As a corollary, this detection algorithm can completely answer whether a given set of three-dimensional absolute spatial relationships is consistent.

### MSC:

 68P15 Database theory 94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
Full Text: