Abstract
This paper studies the expressivity and computational complexity of networks of constraints of topological relations together with convexity. We consider constraint networks whose nodes are regular regions (a regular region is one equal to the closure of its interior) and whose constraints have the following forms: (i) the eight “base relations” of [12], which describe binary topological relations of containment and adjacency between regions; (ii) the predicate, “X is convex.” We establish tight bounds on the computational complexity of this language: Determining whether such a constraint network is consistent is decidable, but essentially as hard as determining whether a set of comparable size of algebraic constraints over the real numbers is consistent. We also show an important expressivity result for this language: If r and s are bounded, regular regions that are not related by an affine transformation, then they can be distinguished by a constraint network. That is, there is a constraint network and a particular node in that network such that there is a solution where the node is equal to r, but no solution where the node is equal to s.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Allen (1983). Maintaining knowledge about temporal intervals. Comm. ACM 26: 832–843.
S. Basu, R. Pollack, and M.-F. Roy (1994). On the combinatorial and algebraic complexity of quantifier elimination. In Proc. Foundations of Computer Science, pages 632–641. IEEE Computer Society.
B. Bennett (1994). Spatial reasoning with propositional logics. In Proc. of the 4th International Conference on Principles of Knowledge Representation and Reasoning, pages 51–62, Bonn, Germany. Morgan Kaufmann, San Mateo, California.
A. G. Cohn (1995). A hierarchical representation of qualitative shape based on connection and convexity. In A. Frank, editor, Spatial Information Theory: A Theoretical Basis for GIS, Proceedings of COSIT'95, LNCS 988, pages 311–326, Springer Verlag, New York.
A. G. Cohn, D. A. Randell and Z. Cui (1995). Taxonomies of logically defined qualitative spatial relations. In N. Guarino and R. Poli, editors, International Journal of Human-Computer Studies, special issue on Formal Ontology in Conceptual Analysis and Knowledge Representation, 43(5–6): 831–846.
H. S. M. Coxeter (1987). Projective Geometry. (2nd ed.) Springer-Verlag, New York.
B. Faltings (1995). Qualitative spatial reasoning using algebraic topology. In A. Frank, editor, Spatial Information Theory: A Theoretical Basis for GIS: Proceedings of COSIT'95, LNCS 988, pages 17–30, Springer Verlag, New York.
A. Grzegorczyk (1951). Undecidability of some topological theories. Fundamenta Mathematicae 38: 137–152.
B. Mishra (1997). Computational real algebraic geometry. In J.E. Goodman and J. O'Rourke, editors, CRC Handbook of Discrete and Computational Geometry, CRC Series, Discrete and Combinatorial Mathematics, pages 537–558, CRC Press, Boca Raton, Florida.
D. A. Randell and A. G. Cohn (1989). Modelling topological and metrical properties in physical processes. In Proc. of the First International Conference on Principles of Knowledge Representation and Reasoning, pages 357–367, Toronto, Ontario. Morgan Kaufmann, San Mateo, California.
D. A. Randell and A. G. Cohn (1992). Naive topology: modelling the force pump. In P. Struss and B. Faltings, editors, Advances in Qualitative Physics, pages 177–192, MIT Press, Cambridge, Massachusetts.
D. A. Randell, Z. Cui, and A. G. Cohn (1992). A spatial logic based on regions and connection. Third International Conference on Principles of Knowledge Representation and Reasoning, pages 165–176, Boston, MA. Morgan Kaufmann, San Mateo, California.
J. Renz and B. Nebel (1997). On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus, In Proc. of the 15th IJCAI, pages 522–527, Nagoya, Japan.
A. Tarski (1951). A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley, California.
A. Tarski (1956). Sentential calculus and topology. in L. Brouwer, E. Beth, and A. Heyting, editors, Logic, Semantics, Metamathematics, Oxford Clarendon Press.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Davis, E., Gotts, N.M. & Cohn, A.G. Constraint Networks of Topological Relations and Convexity. Constraints 4, 241–280 (1999). https://doi.org/10.1023/A:1026401931919
Issue Date:
DOI: https://doi.org/10.1023/A:1026401931919