From: tr.17687@z991.linuxsc.com   
      
   Richard Damon  writes:   
      
   > On 12/25/22 4:44 PM, Ben Bacarisse wrote:   
   >   
   >> Tim Rentsch  writes:   
   >>   
   >>> Ben Bacarisse  writes:   
   >>>   
   >>>> I'm sorry to be obtuse, but what is the "conventional average"?  The   
   >>>> name makes it sound trivial, but the quadratic time makes me certain   
   >>>> that is isn't.   
   >>>   
   >>> Sorry, I meant to refer to your formulation of average   
   >>>   
   >>>      A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }   
   >>>   
   >>> where 'difference' means the shorter arc length.  This formula   
   >>> matches the result for 'mean' on real numbers.   
   >>>   
   >>>> My "conventional average" algorithm (which is not well thought   
   >>>> out) was to (a) rotate the data set to avoid the 23/0 boundary   
   >>>> (not always possible), (b) take the arithmetic mean, and then (c)   
   >>>> rotate the result back.  E.g. [23,0,1] -> [0,1,2] by adding one,   
   >>>> and the average is mean[0,1,2] - 1 = 0.   
   >>>   
   >>> Yes, if you know where to split the cycle then the answer can be   
   >>> found in O(n) time.  But how can we figure out where to split the   
   >>> cycle?   
   >>   
   >> Well I handily stopped considering this at the stage where I   
   >> assumed there must be a simple way to spot the optimal rotation, so   
   >> I never thought it might have to be quadratic.  Presumably your   
   >> algorithm tries all the offsets and minimises the result.   
   >>   
   >> Looking at it a bit more I can't see a better way (but that might   
   >> be the Ratafia de Champagne).  It feels as if there /should/ be   
   >> one.  In fact it feels as if it should be linear.   
   >   
   > I may have lost track of the problem, but wouldn't the addition of   
   > the points in two-dimensions and finding the center of gravity let   
   > you find the answer in O(N) time?   
      
   Finding the center of mass does give an answer in O(N) time, but   
   the answer it gives doesn't match the metric of minimizing the   
   squares of shorter arc lengths.  The results of the two metrics   
   can be, and usually are, different.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)