Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16160

Re: Another little puzzle

Show all headers | View raw

Richard Damon <Richard@Damon-Family.org> writes:

> On 12/25/22 4:44 PM, Ben Bacarisse wrote:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-21 13:17 -0800
  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-22 04:10 +0000
    Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-24 06:21 -0800
      Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-24 16:53 +0000
        Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-24 17:14 +0000
        Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-24 22:30 +0000
          Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-25 00:02 +0000
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:30 +0000
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:55 +0000
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 00:37 -0800
      Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 00:41 +0000
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 01:05 -0800
          Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 09:30 -0800
          Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 21:44 +0000
            Re: Another little puzzle Richard Damon <Richard@Damon-Family.org> - 2022-12-25 17:59 -0500
              Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:39 -0800
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:18 +0000
            Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:35 -0800
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:49 +0000

csiph-web