
Re: Vectors summing to zero
Posted:
Sep 2, 2010 8:43 AM


On Sep 2, 5:16 pm, achille <achille_...@yahoo.com.hk> wrote: > > How about a dot product based strategy like this: > > Let's say you have N ndim vectors v_1 .. v_N. First compute > the N(N+1)/2 inner products D_ij = v_i . v_j and store them > somewhere, then loop over all possible combinations of i<j<k: > > If you want to test whether v_1 + v_2 + v_3 = 0 > as vectors, you check: > > D_11 + 2*D_12 + 2*D_13 > + D_22 + 2*D_23 > + D_33 = 0 > > If you want to test whether v_1, v_2, v_3 are coplanar, > you check: > > det( D_ij ) = 0 ( 1 <= i,j <= 3 ) > > With a little bit more effort, you can implement > collinear test using D_ij in a similar manner. > > In practice, due to round off error, above tests will > not be met exactly. However, you can use it as a fast > filter (once you have D_ij) before carrying out a more > accurate test on the vectors directly.
You're looping over i, j, k, so you have a O(N^3) algorithm. My idea of computing all v_i + v_j, sorting them, then searching for v_k in the list, is O(N^2 log N).  GM

