AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Reasoning with Lines in the Euclidean Space
Khalil Raymond Challita

Last modified: 2009-06-25

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.

Full Text: PDF