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

Groups > comp.programming > #16161

Re: Another little puzzle

Show key headers only | 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?

Yes.  It's been generally agreed that the vector average is the simplest
way to go.  Not only is it simple, it gives an answer to the question
when there is no meaningful average (the zero vector), and an indication
when the average is "unreliable" (a very short vector).

But there is another, one dimensional, average that minimises the sum of
the squares of the short-arc distances to all the data points.  It has
been argued that this average might be less surprising to users, but
it's tricky to calculate -- at least my first thoughts were way too
optimistic.  Tim has an algorithm for it but I don't know what his
method is.

-- 
Ben.

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