Path: csiph.com!news.mixmin.net!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: Another little puzzle Date: Mon, 26 Dec 2022 03:18:44 +0000 Organization: A noiseless patient Spider Lines: 53 Message-ID: <87mt7aonsb.fsf@bsb.me.uk> References: <86pmcczcak.fsf@linuxsc.com> <87wn6krsc5.fsf@bsb.me.uk> <868riwzxu3.fsf@linuxsc.com> <87y1qwpb5p.fsf@bsb.me.uk> <86mt7byhtp.fsf@linuxsc.com> <87zgbbnopo.fsf@bsb.me.uk> <9B4qL.136612$iS99.124371@fx16.iad> MIME-Version: 1.0 Content-Type: text/plain Injection-Info: reader01.eternal-september.org; posting-host="92e13d90ce76510d38a7684020727d43"; logging-data="3298315"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/AC2eSxZwLTxY1a5g0F3fmtjzoMiJ2zqQ=" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) Cancel-Lock: sha1:p9qcKvqIq9mdd7egIW1TkvOn2E0= sha1:m13djtL+ucItF1Nh287qYVL27DY= X-BSB-Auth: 1.115a0e1589f6ce85f77f.20221226031844GMT.87mt7aonsb.fsf@bsb.me.uk Xref: csiph.com comp.programming:16161 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? 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.