Combining Topological and Qualitative Size Constraints for Spatial Reasoning
Alfonso Gerevini, Jochen Renz · 1998
. Information about the relative 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 combine a simple framework for reasoning about qualitative size relations with the Region Connection Calculus RCC-8, a widely studied approach for qualitative spatial reasoning with topological relations. Reasoning about RCC-8 relations is NP-hard, but a large maximal tractable subclass of RCC-8 called b H8 was identified. Interestingly, any constraint in RCC-8 \\Gamma b H8 can be consistently reduced to a constraint in b H8 , when an appropriate size constraint between the spatial regions is supplied. We propose an O(n 3 ) time path-consistency algorithm based on a novel technique for combining RCC-8 constraints and relative size constraints, where n is the number of spatial regions. We prove its correctness and completeness for deciding consistency when the input contains topological ...