---
title: "Reasoning with Lines in the Euclidean Space"
authors:
  - "Khalil Challita"
doi: ""
url: "https://ijcai.org/proceedings/2009/84"
pdf: "https://ijcai.org/proceedings/2009/0084.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "462-466"
track: ""
keywords:
---

# Reasoning with Lines in the Euclidean Space

Khalil Challita

*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