Reasoning with Lines in the Euclidean Space

1 Introduction

During the last three decades, a wide variety of formalisms concerning qualitative spatial reasoning have been proposed and extensively studied by researchers whose main interests lie in the field of artificial intelligence [Clarke, 1985; Randell et al., 1992; Ligozat, 1998; Skiadopoulos and Koubarakis, 2004]. The fact is that most of the spatial information we encounter in our everyday's life can be modeled qualitatively, rather than quantitatively. An overview of qualitative spatial representation and reasoning, as well as current topics in qualitative reasoning can be found in [Cohn and Hazarika, 2001] and [Bredeweg and Struss, 2003], respectively.

Besides its natural association with qualitative temporal reasoning [Wolter and Zakharyaschev, 2000; Renz and Ligozat, 2005; Renz, 2007], qualitative spatial reasoning plays a central role in other fields such as mathematics [Liu, 1998; Moratz et al., 2000] and logics [Gabelaia et al., 2005; Kontchakov et al., 2008]. It is worth noting that few spatial models that are related to elementary geometry have been introduced so far in the field of AI, despite the fact that we find it very interesting to study constraint satisfaction problems whose variables are elementary mathematical structures. Indeed, Balbiani and Tinchev [2007] studied lines in the Euclidean plane and showed that the satisfiability problem of any finite and path-consistent network of lines in the Euclidean plane can be solved in polynomial time. A similar problem that was partially solved [Balbiani and Challita, 2004] concerned lines in the Euclidean space, where we proved that the satisfiability problem of any finite and pathconsistent network of lines in the Euclidean space is NP-hard. In this paper we determine an upper bound for that problem by proving that it is in the class NP, and thus NP-complete. In order to achieve our aim, we follow a slightly different approach than the usual one: instead of providing a nondeterministic polynomial-time algorithm that solves any instance of that problem, we first establish that a particular instance of this problem belongs to the class NP, 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. In other words, we only prove in this paper the existence of a nondeterministic polynomial-time algorithm that solves our problem by providing an upper bound on the number of possible instantiations of a networks variables.

The reason behind using this strategy is that providing a nondeterministic polynomial-time algorithm for this problem turned out to be a nontrivial task.

This paper is divided as follows. We give in section 2 the terminology needed to qualitatively compare lines in the Euclidean space, and then recall some results about lines in dimension three. In section 3, we study particular spatial networks and show that instantiating any of their variables is bounded by a polynomial. Then, in section 4, we prove that the consistency problem of these networks is NP-complete, before extending in section 5 the same result to any spatial network. Finally, we conclude in section 6.

2 Lines in dimension 3

Four basic relations are needed to compare qualitatively two lines in the Euclidean space. We denote them by PO,EQ,DC,NC, which respective meanings are: "having one point in common", "equal", "parallel and distinct", and "non coplanar". Two lines in the space, denoted by l and l′ , can be exactly in one of the following relations: l{PO}l′, l{EQ}l′, l{DC}l′, l{NC}l′. Let E = {PO, EQ, DC, NC} be the set of the jointly exhaustive and pairwise disjoint relations that compare the position of any couple of lines in the Euclidean space.

The definitions needed for describing a constraint satisfaction problem (CSP) can be found in [Montanari, 1974]. We next recall some of them.

A network of linear constraints N is a couple (I,C), where I ⊆ N is a finite set of variables, and C is a mapping from I 2 to the set of the subsets of E (i.e. 2E ). The network N is atomic if for all i, j ∈ I, Card(C(i, j)) > 1 then C(i, j) = E. We say that N is path-consistent if for all i, j ∈ I, C(i, j) ⊆ C(i, k) ◦ C(k, j), for every k ∈ I. A scenario (or an instantiation) is a function f that maps I to a set of lines in the Euclidian space. An instantiation is consistent if, for all i, j ∈ I, the relation satisfied between the lines li = f(i) and lj = f(j) is in C(i, j).

The algorithm of path consistency is explored and analyzed in [Mackworth, 1977; Mackworth and Freuder, 1985]. The constraint propagation algorithm due to Allen [1983], that replaces each constraint C(i, j) by C(i, j)∩(C(i, k)◦C(k, j)), transforms in polynomial time a finite network N into a pathconsistent one, whose set of consistent scenarios is the same as the one for N.

For the rest of this paper, a constraint network will be denoted by N = (V,C), where V = {v1, . . . , vn} is a finite set of variables of N, and C is a mapping from V 2 to 2E . Without loss of generality, we assume in this paper that N is a complete network. This will allow us to instantiate the variables of N more easily, as we shall see later on in sections 3 and 4.

Definition 1 A network of linear constraints N = (V,C) is complete if the following condition holds: for any couple u, v of its variables, there exists a constraint between u and v.

Notice that any network of constraints can be transformed into an equivalent complete network, using a polynomialtime algorithm.

Indeed, let N be a path-consistent constraint network of lines in the Euclidean space. For each node v ∈ V of this network, we check whether for all u ∈ V such that u ̸= v, there is a constraint C(v, u) between v and u. If this is not the case for a particular node u, then we can add the constraint {PO, EQ, DC, NC} between v and u.

Definition 2 A spatial network is a finite and path-consistent linear constraint network of lines in the Euclidian space.

We next recall two results established in [Balbiani and Challita, 2004]: the composition table given in figure 1 and proposition 1.

Proposition 1 The consistency problem of spatial networks is NP-hard.

To prove that the problem of finding a consistent instantiation of a spatial network is NP-complete, we still have to show that it is in the class NP. Addressing the problem in its generality (i.e. when considering any spatial network N) seems to be very difficult because of the multitude of possible instantiations of the variables of N. The problem is that to find a consistent instantiation of N, one might have to instantiate some of its variables several times which, in some cases, could require an exponential time.

Example 1 Consider the case of a network where three of its variables (v1, v2, v3) are constrained by the relation PO. We cannot tell in advance which instantiation of these variables would be consistent. If another variable v is in the relation PO with them, then we deduce that lines l1, l2, l3 must be coplanar. On the other hand, if v is in the relation PO with two of them and NC with the third one, then lines l1, l2, l3 should intersect in a single point without being all coplanar.

3 Particular spatial networks

We consider in this section some particular spatial networks. More precisely, we determine the number of possibilities to consistently instantiate the kth variable of each of these networks.

Definition 3 For any basic relation R ∈ {EQ, PO,DC,NC}, let N n,n′ R = (V,C) be a finite and complete network of constraints such that |V | = n′ ≥ n and where the relation that holds between any couple of its first n variables is R.

In the following subsections, we determine an upper bound for the problems of consistently instantiating spatial networks of the formN n,n′ PO , N n,n′ NC , and N n,n′ DC ; the case of N n,n′ EQ being trivial.

Note that in order to determine the number of possible instantiations of the kth variable of N n,n′ R , (1 ≤ k ≤ n), we take into account all the possible relations that might constraint vk+1 to the previously instantiated variables. From now on, the Euclidean plane defined by two distinct lines lj and lj′ will be denoted by Pj,j′ .

3.1 Networks of the formN n,n′ PO

Question 1 Assuming that we already instantiated n-1 variables of N n,n′ PO , howmany possibilities are there to instantiate the nth one?

Since all the lines l1, . . . , ln-1 should intersect with each other, we distinguish 2 cases when instantiating vn:

1. Case 1. The previous lines are not included in one single plane.

In this case all the lines must intersect in one single point. So ln must also pass through that point, and can be included (or not) in any plane already defined by two lines lj, lj′ , where 1 ≤ j, j ′ ≤ n - 1.

The total number of such planes is equal to ∑n-2 i=1 i+1, where the (+1) denotes the choice of drawing ln outside of the planes Pj,j′ .

Note that the case where ln is included in a plane defined by three (or more) lines is a special case of saying that ln is included in a plane defined by just two of those three

(or more) lines. That is why we just considered planes defined by 2 lines.

1. Case 2. All the previous lines are included in the same plane P . We distinguish two subcases:
2. (a) All the lines intersect in one single point p. We have three possibilities for ln:
3. Line ln is not coplanar with the previous lines.
4. Line ln is coplanar with the previous lines and passes through p.
5. Line ln is coplanar with the previous lines and does not pass through p.
6. (b) They do not intersect in one single point.

In this case ln must also be included in P. Let pj,j′ ∈ P, where 1 ≤ j, j ′ ≤ n - 1, be the point of intersection of lines lj and lj′ . Note that the total number of such points is at most equal to ∑n-2 i=1 i = O(n2 ).

We distinguish three subcases:

1. Line ln passes through two different points: pj,j′ and pk,k′ .
2. Line ln passes throughone point pj,j′ , where 1 ≤ j, j ′ ≤ n - 1.
3. Line ln intersects all the previous lines without passing through any point pj,j′ that belongs to two or more lines.

It is easy to see that the worst case happens for subcase (b) in case 2; and that the total number of different possibilities of drawing line ln is bounded by O(n4 ).

Answer 1. The number of possibilities is bounded by O(n4 ).

3.2 Networks of the formN n,n′ NC

Question 2 Assuming that we already instantiated n-1 variables of N n,n′ NC , howmany possibilities are there to instantiate the nth one?

Suppose that all the previous lines have been drawn in p ≥ 1 groups G1, . . . ,Gp, where for all the lines that belong to the same group Gk, there exists a line lk in the space that intersects them all. Note that line lk is different from lk, which is the instantiation of the variable vk; and that a line lk can, at the same time, belong to several groups Gσ1 , . . . , Gσr where 1 ≤ σi ≤ p.

Line ln can be included in any of these groups or it can be part of a new one. In the former case we have p possibilities, whereas in the latter case line ln could form a new group Gp+1 with any couple of lines amongst l1, . . . , ln-1, and such that line lp+1 could be in the relation DC, NC, or PO with one or more of the lines l1, . . . , lp and l1, . . . , ln-1 (this condition will help us determine the direction of lp+1 ). We know that there are C2n-1 = O(n2 ) ways of forming groups of two lines amongst l1, . . . , ln-1. Moreover, there are O(n2 ) directions for line lp+1 . Assuming that p = O(n), we conclude that:

Answer 2. The number of possibilities is bounded by O(n5 ).

3.3 Networks of the formN n,n′ DC

Question 3 Assuming that we already instantiated n-1 variables of N n,n′ DC , howmany possibilities are there to instantiate the nth one?

This is probably the most difficult case to deal with. Indeed, a variable vn+1 could be in the relation PO with k ≥ 2 other variables of a network N ′ and with the relation NC with the remaining ones.

We next assume that the first n - 1 lines have been drawn in p parallel planes P1, . . . , Pp; where each plane Pi contains ki lines, for a total of ∑pi=1 ki = n - 1 lines.

We next describe all the qualitative ways to draw line ln.

Line ln could be drawn in any plane Pi or in a new one. Moreover, one of the following cases holds:

1. Line ln could be included in a plane Pj,j′ defined by 2 existing lines lj and lj′ , where 1 ≤ j, j ′ ≤ n - 1;
2. Or it could be included in a plane P parallel to Pj,j′ defined by 2 existing lines lj and lj′ , where 1 ≤ j, j ′ ≤ n - 1, and such that P contains another line lj′′ (with 1 ≤ j ′′ ≤ n-1, and j ′′ ̸= j, and j ′′ ̸= j ′ ).

It is easy to see that the number of possibilities of drawing line ln in case 2 is greater than the one of drawing it in case 1. Indeed, after fixing a plane Pj,j′ , we have O(n) possibilities of selecting a third line lj′′ that satisfies the conditions of case 2.

We next determine the total number of possibilities (denoted by S) of drawing line ln in case 1.

Remark 1 Taking into account case 2 would lead us to multiply S by n.

Let us assume that ln is drawn in a plane Pm, where 1 ≤ m ≤ p. The number of different possibilities to draw it is given by:

The double-sum takes into account all the possible planes Pj,j′ that might contain ln. The (+1) denotes the choice of drawing ln outside of all the planes Pj,j′ and in a new plane Pp+1 .

Since we can draw ln in any of the planes P1, . . . , Pp, we deduce that the overall number of possibilities to draw it in any plane Pj,j′ is:

As we can see from equation 2, and because of the factor kikj, the total number of possible instantiations of a constraint network N n,n′ DC depends on the way the lines are distributed in the parallel planes Pi, 1 ≤ i ≤ p (see Appendix A).

Proposition 2 The total number of possible instantiations of the nth variable of N n,n′ DC is bounded by O(n6 ).

Proof 1 We first notice that the complexity of the sum S is the same as its leading term S ′ , where:

We then consider the worst case where we assume that the lines are distributed over p planes with p = O(n), and that the number of lines in each plane Pi depends on n too (i.e. ki = O(n), for all i ∈ {1, . . . , p}).

For all i, j ∈ {1, . . . , p}, we have kikj = O(n2 ). Thus, the double sum in S ′ is bounded by O(n4 ). Since S ′ is the leading term of S and that p = n, we deduce that S = O(n5 ); and hence conclude that the total number of possible instantiations of N n,n′ DC is bounded by nS = O(n6 ) (refer to Remark 1).

Answer 3. The number of possibilities is bounded by O(n6 ). The next proposition follows from the results established in this section.

The total number of possible instantiations of the kth variable of N n,n′ R , where 1 ≤ k ≤ n, is bounded by O(k6 ).

Indeed, the worst case happens when we consider networks of the formN n,n′ DC .

The method we described here enlightens us on how to prove that the consistency problem of particular spatial networks is in NP, which is the subject of the next section.

4 NP-completeness results

We first prove in this section that the consistency problem of some of the particular networks (i.e. N n,n+1 R ) we saw in section 3 is NP-complete, and then we extend this result to any finite spatial network.

To establish proposition 4, one must provide a nondeterministic polynomial-time algorithm that solves the consistency problem of each of the particular networks we previously described. The aim of the following algorithms is to prove proposition 4.

4.1 N n,n+1 DC networks

In the below pseudo-code, pi denotes the number of parallel planes that are used to draw lines l1 to li-1; kj is equal to the number of lines drawn in the plane Pj; and Pr1,r2 represents the plane defined by the lines lr1 and lr2 .

In the below algorithms, by "randomly number the variables of N n,n R " we mean that any numbering of the first n variables of these networks would work. Moreover, by "guess a number q" we mean "nondeterministically select a line lq or a plane Pq", depending on the context.

Algorithm 1. Given N n,n+1 DC :

1 randomly number t he v a r i a b l e s of N n,n DC ; 2 for i = 1 to n 3 guess a number q between 0 and pi ;

4

5

6

7

8

9

10

11

12

13

14

guess a number n0 between 1 and 2 ; i f n0 = 1 then {guess q′ ̸= q and q′′ ̸= q between 1 and pi ; guess r1 ∈ {0, 1, . . . , kq′} and r2 ∈ {0, 1, . . . , kq′′} ; draw li i n t he p l ane Pq , where li i s i nc l uded i n Pr1,r2 ; } e l s e {guess q′ ̸= q and q′′ ̸= q between 1 and pi ; guess r1 ∈ {0, 1, . . . , kq′} and r2 ∈ {0, 1, . . . , kq′′} ; guess a number r0 between 1 and n-1 ; draw li i n Pq and Pr0 where Pr0 //Pr1,r2 ; 15 draw ln+1 ; }

Intuitively, q represents the plane Pq in which to draw line li. If q = 0, then li is drawn in a new plane parallel to the other ones.

Furthermore, in the first case where n0 = 1, we guess the planes (i.e. Pq′ and Pq′′ ) that contain the lines (i.e. lr1 and lr2 ) defining the plane that should include li.

Note that if r1 = 0 or r2 = 0, then the line li is drawn in plane Pq but is not included in any plane defined by two existing lines lj , lj′ , where 1 ≤ j, j ′ ≤ i - 1.

The second case, where n0 = 2 is similar to the first one except that on line 13 we guess a line lr0 such that Pr0 contains li and is parallel to Pr1,r2 .

Note that drawing ln+1 is straightforward and is based on the constraints of vn+1 with all the previous variables of N n,n+1 DC . It is easy to see that the running time of this algorithm is polynomial in the size of the spatial networkN n,n DC .

Remark 2 During iteration i, it is worth noting that keeping track of all the planes Pj,j′ that are defined by all the couple of lines lj, lj′ , where 1 ≤ j, j ′ ≤ i - 1, requires polynomial space; and hence our algorithm would belong to the class NPSPACE. 1

Question 4 A fundamental question is:

How to draw line li in a plane Pq in such a way that it is not included in any plane defined by an already existing two lines lj , lj′ , with 1 ≤ j, j ′ ≤ i -1, and without keeping track of all the planes Pj,j′ ?

Answer 4.

The trick lies in the way we actually draw line li in the Euclidean space, and the fact that the number of lines we already drew is finite.

We start by selecting for example the rightmost line (denoted by lr) amongst all the lines included in the planes (Pj )1≤j≤pi . We then draw li inside the plane Pq and to the right of the vertical plane to Pq that passes through lr.

In this way we are sure to answer question 4 by just keeping track of one line (in this case the rightmost one).

Thus proposition 4 holds for the case where R = DC.

4.2 N n,n+1 PO networks

We next provide a nondeterministic polynomial-time algorithm that solves spatial networks of the formN n,n+1 PO .

1 We know by Savitch's theorem [Savitch, 1970] that NPSPACE = PSPACE, but this is not of help for us since we do not know whether PSPACE ⊆ NP .

Algorithm 2. Given N n,n+1 PO :

1 randomly number t he v a r i a b l e s of N n,n PO ; 2 for i = 1 to n 3 guess a number n0 between 1 and 2 ; 4 i f n0 = 1 then 5 { guess two p o i n t s pj,j′ and pk,k′ or none ; 6 draw li such t h a t i t pa s se s through pj,j′ 7 and pk,k′ ; } 8 e l s e 9 { guess r1 ∈ {0, 1, . . . , i -1} 10 and r2 ∈ {0, 1, . . . , i -1} ; 11 i f ( r1 = 0 or r2 = 0 or r1 = r2 ) 12 then draw li i n a new p l ane ; 13 e l s e draw li i n t he p l ane Pr1,r2 ; 14 draw ln+1 ; }

Intuitively, the case where n0 = 1 (resp. n0 = 0) corresponds to the fact that all the lines are included in the same plane (resp. intersect in one point).

On line 5, if we guess the same point (resp. we guess none) then subcase (b) (resp. (c)) of case 2 in subsection 3.1 applies. Moreover, during iteration i we just need to keep track of the last line that was drawn in a new plane (denoted by lnew,i). This would save us from using polynomial-space to keep track of all the possible planes that can be defined by two lines lj, lj′ .

The idea is to draw all the new lines (that must pass through a single point) with, for example, a slight rotation to the right with respect to lnew,i, and in such a way not to exceed an angle of 900 with l1.

It is easy to see that proposition 4 holds for the case where R = PO.

We next provide a nondeterministic polynomial-time algorithm that solves spatial networks of the formN n,n+1 NC .

Algorithm 3. Given N n,n+1 NC :

1 randomly number t he v a r i a b l e s of N n,n NC ; 2 for i = 1 to n 3 guess 1 number r1 ∈ {0, 1, . . . , σi} ; 4 i f ( r1 ̸= 0) 5 then draw li i n group Gr1 ; 6 e l s e 7 {guess r1, r2 ∈ {1, . . . , i -1} ; 8 guess q0 i n {1, . . . , i -1} or i n {1, . . . , σi} ; 9 guess q′0 i n {0, 1, 2} ; 10 draw li i n a new group de f i ned by 11 lr1 , lr2 and lσi+1 ; 12 draw ln+1 ; }

Recall that on line 5, when li is drawn in group Gr1 , this means that it intersects with lr1 (cf. subsection 3.2).

On line 7, we guess 2 lines with which li forms a new group Gσi+1. Steps 8 and 9 help us determine the direction of lσi+1 based on its relationship with line lq0 . We have 3 possibilities: DC, NC and PO. For example, q′0 = 0 could mean that lσi+1 is in the relation DC with lq0 .

It is easy to see that proposition 4 holds for the case where R = NC.

Proposition 4 The consistency problem of N n,n+1 R , where R ∈ {EQ, PO, DC, NC}, is NP-complete.

Actually, there exists a deterministic polynomial-time algorithm that solves the consistency problem of N n,n+1 R (e.g. it suffices to start by instantiating vn+1). But our idea of using a nondeterministic algorithm to instantiate the kth variable of N n,n+1 R allows us to generalize the result established in the above proposition to any network N n,n′ R .

5 Extending the result to any finite spatial network

In this section, we show that the consistency problem of any finite spatial network is NP-complete. Recalling proposition 3, we have:

Fact 1 Let N ′ = N n,n′ R , where R ∈ {EQ, PO,DC,NC}. For any k ∈ {1, 2, . . . , n′}, the number of different instantiations of vk in N ′ is bounded by O(k6 ).

Indeed, it is easy to see that the more different types of constraints a spatial network has, the less consistent instantiations its variables have.

For example, let N ′ = N 3,4 PO and N ′′ = N 4,4 PO be two spatial networks where the fourth variable of N ′ is in the relation DC with v′1 and in the relation PO with v′2 and v′3 . The constraint DC forces all the lines (l′1 to l′4 ) to belong to the same plane. We can easily see that the number of consistent instantiations of N ′ is less than that of N ′′ .

When instantiating the kth variable of N ′ , and assuming that the first k - 1 variables are constrained with each other with the same relation R, we distinguish two cases:

1. The constraints that relate vk to all the previous k - 1 variables are all equal to R;
2. There exists at least one constraint that relates vk to another variable vk′ (k′ < k) that is different fromR;

Thus, it is easy to see that there are less possible instantiations of vk in the latter case than in the former case because of the constraint Cvk,vk′ .

Proposition 5 Let N be a finite spatial network.

The problem of finding a consistent instantiation of N is NPcomplete.

Proof 2 The proof of this proposition follows directly from fact 1 and from noticing that any finite spatial network belongs to the set:

We conclude this section by stating that there exists a nondeterministic polynomial-time algorithm that solves the consistency problem of N .

6 Conclusion

In this paper, we showed that the consistency problem of finite and path-consistent constraint networks of lines in the Euclidean space is NP-complete. To achieve our aim, we first proved the above result for particular spatial networks, and then extended it to any spatial network. As we already stated in the introduction, we did not provide explicitly a nondeterministic polynomial-time algorithm that solves the consistency problem of a spatial network, but rather proved the existence of such an algorithm.

Our next aim is to try to provide an explicit algorithm that solves this problem. Moreover, we intend to find an answer to the following questions: would the consistency problem of lines in the Euclidean space remain the same in the case of infinite networks? What are all the tractable subclasses of this formalism? For the time being, all we know is that if we remove the basic relation NC, the consistency problem of lines in the Euclidean plane becomes tractable.