---
title: "Topological Inference"
authors:
  - "Michelangelo Grigni"
  - "Dimitris Papadias"
  - "Christos H. Papadimitriou"
doi: ""
url: "https://ijcai.org/proceedings/1995/117"
pdf: "https://ijcai.org/proceedings/1995/0117.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "901-906"
track: "Knowledge Representation"
keywords:
---

# Topological Inference

Michelangelo Grigni, Dimitris Papadias, Christos H. Papadimitriou

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 901-906.

## Abstract

Geographical database systems deal with certain basic topological relations such as "A overlaps B" and "B contains C" between simply connected regions in the plane. It is of great interest to make sound inferences from elementary statements of this form. This problem has been identified extensively in the recent literature, but very limited progress has been made towards addressing the considerable technical difficulties involved. In this paper we study the computational problems involved in developing such an inference system. We point out that the problem has two distinct components that interact in rather complex ways: relational consistency, and planarity. We develop polynomial-time algorithms for several important special cases, and prove almost all the others to be NP-hard.