Reasoning with Lines in the Euclidean Space
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 462-466.
Abstract
The main result of this paper is to show that the problem of instantiating a finite and path-consistent constraint network of lines in the Euclidean space is NP-complete. Indeed, we already know that reasoning with lines in the Euclidean space is NP-hard. In order to prove that this problem is NP-complete, we first establish that a particular instance of this problem can be solved by a nondeterministic polynomial-time algorithm, and then we show that solving any finite and path-consistent constraint network of lines in the Euclidean space is at most as difficult as solving that instance.Khalil Raymond Challita
@inproceedings{ijcai2009p84,
title = {Reasoning with Lines in the Euclidean Space},
author = {Challita, Khalil},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {462--466},
year = {2009},
url = {https://ijcai.org/proceedings/2009/84},
}
TY - CPAPER TI - Reasoning with Lines in the Euclidean Space AU - Challita, Khalil T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 462 EP - 466 UR - https://ijcai.org/proceedings/2009/84 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
