On August 2, 2008, Matthew Toseland wrote: > On Saturday 02 August 2008 02:41, Ed Tomlinson wrote: > > 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 > > You miss the point. We already have what is effectively an angle, it's just > in > 0 to 1 instead of 0 to 360 deg / 2*pi rads. The problem is the circular > keyspace.
No I have _not_ missed the point. If you map each key onto the rim of a circle and average resulting the x and y coords of all the keys you get an average in a circular keyspace. Try it. If fact radius of the averaged x, y will also be a measure of just how specialized your store is... (eg r = sqrt(average(x cords)^2+average(y cords)^2) Ed