Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Vectors summing to zero
Replies: 24   Last Post: Sep 9, 2010 8:48 AM

 Messages: [ Previous | Next ]
 gerry@math.mq.edu.au Posts: 304 Registered: 12/11/06
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 n-dim 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