Reasoning with Lines in the Euclidean Space
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
Cite
Text
Challita. "Reasoning with Lines in the Euclidean Space." International Joint Conference on Artificial Intelligence, 2009.Markdown
[Challita. "Reasoning with Lines in the Euclidean Space." International Joint Conference on Artificial Intelligence, 2009.](https://mlanthology.org/ijcai/2009/challita2009ijcai-reasoning/)BibTeX
@inproceedings{challita2009ijcai-reasoning,
title = {{Reasoning with Lines in the Euclidean Space}},
author = {Challita, Khalil},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2009},
pages = {462-467},
url = {https://mlanthology.org/ijcai/2009/challita2009ijcai-reasoning/}
}