Qualitative Spatial Reasoning with Topological Information

1. Front Matter

   Pages I-XVII

   PDF

2. Introduction

   Pages 1-11

3. Background

   Pages 13-29

4. Qualitative Spatial Representation and Reasoning

   Pages 31-40

5. The Region Connection Calculus

   Pages 41-50

6. Cognitive Properties of Topological Spatial Relations

   Pages 51-64

7. Computational Properties of RCC-8

   Pages 65-116

8. A Complete Analysis of Tractability in RCC-8

   Pages 117-130

9. Empirical Evaluation of Reasoning with RCC-8

   Pages 131-154

10. Representational Properties of RCC-8

    Pages 155-172

11. Conclusions

    Pages 173-177

12. A. Enumeration of the Relations of the Maximal Tractable Subsets of RCC-8

    Pages 179-190

13. Back Matter

    Pages 191-207

    PDF

Spatial knowledge representation and reasoning with spatial knowledge are relevant issues for many application areas such as robotics, geographical information systems, and computer vision. Exceeding purely quantitative approaches, more recently initiated qualitative approaches allow for dealing with spatial information on a more abstract level that is closer to the way humans think and speak.
Starting out with the qualitative, topological constraint calculus RCC8 proposed by Randell, Cui, and Cohn, this work presents answers to a variety of open questions regarding RCC8. The open issues concerning computational properties are solved by exploiting a broad variety of results and methods from logic and theoretical computer science. Questions concerning practical performance are addressed by large-scale empirical computational experiments. The most impressive result is probably the complete classification of computational properties for all fragments of RCC8.

• Performance
• classification
• computer vision
• information system
• knowledge
• knowledge representation
• robot
• robotics

• Dept.of Computer Science, Database and AI Group, Vienna University of Technology, Wien, Austria

  Jochen Renz

Policies and ethics