Constraint Networks of Topological Relations and Convexity

Ernest Davis, Nicholas Mark Gotts, Anthony G. Cohn

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)241-280
Number of pages40
JournalConstraints
Volume4
Issue number3
DOIs
StatePublished - 1999

Keywords

  • Complexity
  • Constraints
  • Convexity
  • Expressivity
  • RCC8
  • Topology

ASJC Scopus subject areas

  • Software
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Constraint Networks of Topological Relations and Convexity'. Together they form a unique fingerprint.

Cite this