Finding minimal and maximal sets of spatial relationships in pictorial retrieval systems. (English) Zbl 1110.68380

Zhang, Qinglong; Yau, Stephen S.-T.

Commun. Inf. Syst. 5, No. 3, 311-340 (2005).

Summary: Spatial reasoning is an important component in pictorial retrieval systems. There are two approaches to handling spatial relationships: the well-known one is to use algorithms on which most earlier work is based, and the recent one is to construct deductive rules that allow spatial relationships to be deduced. A. P. Sistla, C. Yu and R. Haddad [“Reasoning about spatial relationships in picture retrieval systems”, in: Proc. 20th Int. Conf. Very Large Databases, Santiago, Chile, 570–581 (1994)] developed a system of rules \({\mathcal R}\) on reasoning about basic spatial relationships that are of common interest in pictorial databases. In this paper, we consider the following two problems with that system of rules \({\mathcal R}\): the deduction problem (that is, to deduce new spatial relationships from a given set F of spatial relationships) and the reduction problem (that is, to eliminate redundant spatial relationships from F.
We use the mathematically simple matrix representation approach to show that these two problems can be solved by efficient (i.e., polynomial-time) algorithms. The time required by both of them is at most a constant multiple of the time to compute the transitive reduction of a directed graph with \(n\) vertices or to compute the transitive closure of a directed graph with \(n\) vertices or to perform \(n\times n\) 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.

MSC:

68P20	Information storage and retrieval of data
94A08	Image processing (compression, reconstruction, etc.) in information and communication theory
68U10	Computing methodologies for image processing

Keywords:

spatial reasoning