On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

Kontchakov, Roman; Nenov, Yavor; Pratt-Hartmann, Ian; Zakharyaschev, Michael

doi:10.5591/978-1-57735-516-8/IJCAI11-165

On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann, Michael Zakharyaschev

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 957-961.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-165

Abstract

We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates as well as Boolean operations on regions, interpreted over 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. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in the Euclidean plane, NP-complete over regular closed sets in three-dimensional Euclidean space, and ExpTime-complete over polyhedra in three-dimensional Euclidean space.

Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann, and Michael Zakharyaschev. 2011. On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 957–961. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-165

@inproceedings{ijcai2011p165,
  title     = {On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces},
  author    = {Kontchakov, Roman and Nenov, Yavor and Pratt-Hartmann, Ian and Zakharyaschev, Michael},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {957--961},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-165},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-165},
}

TY  - CPAPER
TI  - On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces
AU  - Kontchakov, Roman
AU  - Nenov, Yavor
AU  - Pratt-Hartmann, Ian
AU  - Zakharyaschev, Michael
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 957
EP  - 961
DO  - 10.5591/978-1-57735-516-8/IJCAI11-165
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-165
ER  -