From: ben.usenet@bsb.me.uk   
      
   Tim Rentsch  writes:   
      
   > Ben Bacarisse  writes:   
   >   
   >> 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.   
   >   
   > Right.   
   >   
   >> 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.   
   >   
   > My best so far is only O( n * log n ).  Probably that isn't   
   > optimal.  I don't see how to make it linear though.  Do you have   
   > any ideas?   
      
   No.  I should try with a clear head.   
      
   --   
   Ben.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)