RCC8: Connectedness and Euclidean Spaces
- Speaker: Dr. Roman Kontchakov (Birkbeck College, London)
- Host: Ian Pratt-Hartmann
- 20th November 2013 at 14:00 in Lecture Theatre 1.4, Kilburn Building
RCC8 is a widely-studied formalism for describing topological arrangements of spatial regions, which are standardly understood as regular closed subsets of topological spaces. RCC8, however, lacks the means to say that a spatial region comprises a `single piece?. We study two types of constraints: one expresses connectedness of a region and the other connectedness of its interior. The languages are interpreted over the regular closed and the regular closed semi-linear sets in low-dimensional Euclidean spaces.
We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. In particular, (a) the connectedness predicate can distinguish between arbitrary and semi-linear regular closed subsets of the real line and the satisfiability problems is NP-complete in either case; (b) the interior-connectedness predicate can distinguish between regular closed subsets of the Euclidean plane and polygons and the satisfiability problem in the latter case is NP-complete (in the former case decidability is open); ? the connectedness predicate cannot distinguish between polygons and regular closed subsets of the Euclidean plane and the satisfiability problem is NP-complete; (d) in dimensions 3 and above, connectedness and interior-connectedness do not add anything interesting to RCC8.
(joint work with Ian Pratt-Hartmann and Michael Zakharyaschev)