Topological Inference

Grigni, Michelangelo; Papadias, Dimitris; Papadimitriou, Christos H.

Topological Inference

Michelangelo Grigni, Dimitris Papadias, Christos H. Papadimitriou

Download BibTeX Cite

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Knowledge Representation. 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.

Michelangelo Grigni, Dimitris Papadias, and Christos H. Papadimitriou. 1995. Topological Inference. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95. IJCAI, 901–906. https://ijcai.org/proceedings/1995/117

@inproceedings{ijcai1995p117,
  title     = {Topological Inference},
  author    = {Grigni, Michelangelo and Papadias, Dimitris and Papadimitriou, Christos H.},
  booktitle = {Proceedings of the Fourteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-95}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Chris S. Mellish},
  pages     = {901--906},
  year      = {1995},
  note      = {Knowledge Representation},
  url       = {https://ijcai.org/proceedings/1995/117},
}

TY  - CPAPER
TI  - Topological Inference
AU  - Grigni, Michelangelo
AU  - Papadias, Dimitris
AU  - Papadimitriou, Christos H.
T2  - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1995
SP  - 901
EP  - 906
UR  - https://ijcai.org/proceedings/1995/117
ER  -