|
|
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
|
|
