Combining topological and size information for spatial reasoning

摘要

Information about the size of spatial regions is often easily accessible and, when combined with other types of spatial information, it can be practically very useful. In this paper we introduce four classes of qualitative and metric size constraints, and we study their integration with the Region Connection Calculus RCC-8, a well-known approach to qualitative spatial reasoning with topological relations. We propose a new path-consistency algorithm for combining RCC-8 relations and qualitative size relations. The algorithm is complete for deciding satisfiability of an input set of topological constraints over one of the three maximal tractable subclasses of RCC-8 containing all the basic relations. Moreover, its time complexity is cubic and is the same as the complexity of the best-known method for deciding satisfiability when only these topological relations are considered. We also provide results on finding a consistent scenario in cubic time for these combined classes.