Font Size:

Reasoning with Lines in the Euclidean Space

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.

#### Keywords

Constraint satisfaction problems; Satisfiability; Qualitative spatial reasoning; Euclidean geometry; NP-completeness

Full Text:
PDF