On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces
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 R2, EXPTIME-complete over polyhedra in R3, and NP-complete over regular closed sets in R3.
Cite
Text
Kontchakov et al. "On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-165Markdown
[Kontchakov et al. "On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/kontchakov2011ijcai-decidability/) doi:10.5591/978-1-57735-516-8/IJCAI11-165BibTeX
@inproceedings{kontchakov2011ijcai-decidability,
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 = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {957-962},
doi = {10.5591/978-1-57735-516-8/IJCAI11-165},
url = {https://mlanthology.org/ijcai/2011/kontchakov2011ijcai-decidability/}
}