MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Vector Union

The problem of finding a function to return the union of a list of
n-vectors which is at once *fast* and yet *unfailing* has beguiled me for
several years. I contrived a slow but unfailing 'vunion' function about
five years ago; made a not-so-slow and unfailing version a year ago; and
then found it to occasionally fail when Chop was applied to the vectors
without a second argument.

I posed a programming challenge to the Group a few days ago: make a fast
and unfailing vector union function. David Park and Michael Trott were kind
enough to respond, for which I thank them very much. Around a year around
Martin Kraus also supplied a vector union function.

Good solutions seem to hinge upon *sorting the list of n-vectors*.
Searching the internet, I find that sorting a list of vectors seems to be a
classic problem in computer science. This is where Chop comes into play: to
compare one vector to another, when the components are machine precision,
is easier when very small numbers with opposite signs are Chopped to zero.

My function, slow but sure:

vunion[v_] :=
Union[Chop[v, .000001],
SameTest -> (Sign[#1] == Sign[#2] &&
Chop[#1 - #2, .000001] == Table[0, {Length[v[[1]]]}] & )]

David Park appealed to an "UnorderUnion" function devised by Carl Woll,
which works well on lists with integer and symbolic components. Park uses
Round to put the machine numbers into a form acceptable to UnorderUnion.
The implications of using Round worry me, but Park's method has not failed
yet, given inputs which made most other methods fail. His function is
around twenty times faster than mine. Thanks David!!

(*modified Woll*)
OrderedUnion2[li_] :=
Block[{i}, i[n_] := (i[n] = Null; n);
i /@ li]

vunion2[v_] :=
Block[{accuracylist, v2},
accuracylist = OrderedUnion2[Round[10^5*(v2 = Sort[Chop[v, .000001]])]];
Do[If[accuracylist[[i]] === Null, v2[[i]] = Null], {i, Length[v2]}];
v2 /. Null -> Sequence[]]

Russell Towle
Box 141
Dutch Flat, CA 95714
(530) 389-2872

  • Prev by Date: best fit 3D vector to points with a miss-distance specified
  • Next by Date: Re: Multiple St.St. and Alg-Diff Eq
  • Previous by thread: vector union
  • Next by thread: Re: Vector Union