- #1

- 4

- 0

I apologise if this has been asked before. I did a search, but quite frankly, I'm not even sure what to search for.

My gut feeling is that this problem has already been well defined and solved, so if someone could point me in the proper direction, that would be great.

Consider a set of n vectors which can point in the positive or negative direction: {A1, A2, ... An }

if Ax and Ay point in the same direction, then d(Ax,Ay) = 1.

Similarly, if they point in the opposite direction, then d(Ax,Ay) = -1.

Now if d(A1,A2) = 1, and d(A2,A3) = 1, then d(A1,A3) must equal 1 to be consistent.

Similarly, if d(A1,A4) = 1 and d(A4,A5) = -1, then d(A1,A5) must equal -1 to be consistent.

[I'm guessing for the trivial case of d(Ax,Ax), the answer would be 1]

the problem:

Assume that I'm given all d(Ax,Ay) for x,y = 1...n. What is an efficient way of determining if this set is consistent?

[note: I can do this brute force, but as n gets big, it becomes a mess.]

Thanks!

-Mike.