On August 1, 2008, Michael Rogers wrote:
> Daniel Cheng wrote:
> > in a circular space, we can get infinite number of "average" by changing
> > point of reference. --- choose the point of reference with the smallest
> > standard deviation.
>
> From an infinite number of alternatives? Sounds like it might take a
> while. ;-) I think we can get away with just trying each location as the
> reference point, but that's still O(n^2) running time.
>
> How about this: the average of two locations is the location midway
> along the shortest line between them. So to estimate the average of a
> set of locations, choose two locations at random from the set and
> replace them with their average, and repeat until there's only one
> location in the set.
>
> It's alchemy but at least it runs in linear time. :-)
Another idea that should run in linear time. Consider each key a point on the
edge
of a circle (with a radius of 1). Convert each key (0=0 degress, 1=360) to an
x, y cord and
average these numbers. Once all keys are averaged convert the (x, y) back into
a key to
get the average.
eg x = sin (key * 360), y = cos(key * 360) assuming the angle is in
degrees not radians.
where a key is a number between 0 and 1
Ed
_______________________________________________
Devl mailing list
Devl@freenetproject.org
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
