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

Groups > comp.programming > #16188 > unrolled thread

Re: Another little puzzle

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-30 01:00 +0000
    Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-29 23:25 -0800
      Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-30 14:04 +0000
        Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-31 00:24 +0000
          Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-31 06:42 -0800
            Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-31 17:04 +0100
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-01 01:24 +0000
              Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-08 07:45 -0800
                Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-08 17:17 +0100
                  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 20:41 +0000
                    Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2023-01-08 21:14 +0000
                    Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-08 22:31 +0100
                      Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 03:25 +0000
                        Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-09 11:22 +0100
                          Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 20:37 +0000
                            Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-10 09:06 +0100
                              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-11 02:41 +0000
                                Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-11 10:01 +0100
                                  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-12 01:00 +0000
                  Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-10 23:36 -0800
                    Re: Another little puzzle Y A <ya00000100000@yahoo.com> - 2023-01-11 02:39 -0800
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-01 01:10 +0000
              Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-08 07:17 -0800
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 19:43 +0000
                  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 19:59 +0000
                    Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-10 23:25 -0800
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-31 06:20 -0800
          Re: Another little puzzle Augǝl <angel0000000001000000000000@mail.ee> - 2022-12-31 10:23 -0800

Page 1 of 2  [1] 2  Next page →

#16188 — Re: Another little puzzle

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>I waited a few days before answering to allow 
>>sufficient time to think about the problem.
>
>   (A few lines in this post contain more than 72 characters.)

???  That's an odd thing to say!

>   I sometimes look at records of events like when someone got
>   up or went to bed on different days and wonder about the
>   "average time" he gets up or goes to bed. Some years ago,
>   I asked in another newsgroup how to average times, and from
>   answers there I kept this expression for a spreadsheet and
>   two times in cells A1 and B1:
>
> REST(1.5+1/6.28318530717959*ARCTAN2((COS((A1-0.5)*6.28318530717959)+COS((B1-0.5)*6.28318530717959))/2,(SIN((A1-0.5)*6.28318530717959)+SIN((B1-0.5)*6.28318530717959))/2),1)

I'm not going to try to unravel that (it is most likely the conventional
atan2 of the sum of sines and cosines), but the problem is barely worth
considering for two times.  What did you do with more than two?

>   . I added a bit, like "REST", but the trigonometric part
>   came from that newsgroup. (Times t of a day in spreadsheets
>   often are 0 <= t < 1 because they often use the day as the
>   unit of time). At that time, I did not understand what was
>   going on! In hindsight, today, I see that this seems to
>   calculate the average via the average of the position of 
>   the two points on a 24-hour clock in two dimensions.
>
>   The corresponding Wikipedia page is called, "Mean of circular
>   quantities".
>
>   I also have a copy of a page "Circular Values Math and
>   Statistics with C++11" saved. Other pages I found were
>   "Averages-Mean angle - Rosetta Code", "Averaging Angles -
>   The Math Doctors", or "algorithm - How do you calculate
>   the average of a set of angles - Stack Overflow". Maybe
>   some of these pages can still be found in the Web today.
>
>   There was also another web page that used lines some of
>   which have more than 72 characters. It contained,
>
> |A good way to estimate an average angle, A, from a set of angle measurements
> |a[i] 0<=i<N, is:
> |
> |                   sum_i_from_1_to_N sin(a[i])
> |    a = arctangent ---------------------------
> |                   sum_i_from_1_to_N cos(a[i])

I think it's easier to think in terms of vectors (for one thing you get
a useful magnitude as well).  Also the programmer's atan2 is more
helpful here than the mathematician's arctan.

I found this problem interesting but only later in the discussion as I
have been using this metric for some time.  What got interesting (to me)
was that there is another sound interpretation of the average as
suggested by Tim, ironically prompted but a general definition of what
might constitute an average that I had posted and failed to follow
through on.

So thank you for bringing it up.

> |A very careful study of the properties of this estimator is in the book
> |"Statistics On Spheres", Geoffrey S. Watson, University of Arkansas Lecture
> |Notes in the Mathematical Sciences, 1983 John Wiley & Sons, Inc.

Rant: This book is now out of print and effectively dead.  What a shame.
I can't imagine that either the author or the publisher (John Wiley and
Sons) hold out much hope of making any more money from it, so with
things as they stand, all that person's hard work is now lost to anyone
not lucky enough to have access to a library that happens to have it, or
patient enough to wait (and prepared to pay) for the inter-library loan
system to work it's magic.

And for people no where near any library, tough!

-- 
Ben.

[toc] | [next] | [standalone]

#16191

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

[...]

> I found this problem interesting but only later in the discussion as
> I have been using this metric for some time.  What got interesting
> (to me) was that there is another sound interpretation of the
> average as suggested by Tim, [...]

It wasn't my idea.  I got it from a posting by Mike Terry on
December 21.  I hadn't seen that formulation of arithmetic mean
before and I was amazed that it worked.  So I can't really take
any credit for the suggestion.

> ironically prompted but a general definition of what might
> constitute an average that I had posted and failed to follow
> through on.

I remember your posting as coming after the one by Mike Terry,
and so I thought your comments were derived from his.  Sorry if
my conclusions there were off the mark.

[toc] | [prev] | [next] | [standalone]

#16194

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
> [...]
>
>> I found this problem interesting but only later in the discussion as
>> I have been using this metric for some time.  What got interesting
>> (to me) was that there is another sound interpretation of the
>> average as suggested by Tim, [...]
>
> It wasn't my idea.  I got it from a posting by Mike Terry on
> December 21.  I hadn't seen that formulation of arithmetic mean
> before and I was amazed that it worked.  So I can't really take
> any credit for the suggestion.
>
>> ironically prompted but a general definition of what might
>> constitute an average that I had posted and failed to follow
>> through on.
>
> I remember your posting as coming after the one by Mike Terry,
> and so I thought your comments were derived from his.  Sorry if
> my conclusions there were off the mark.

You are right in that MT posted the same general formulation 9 hours
before I did (though I'd not seen that).  My confusion came from your
explanation, to me, of "conventional average":

  "Sorry, I meant to refer to your formulation of average"

followed by the formula I gave rather than then entirely equivalent one
given by MT.

Anyway, the credit I'm giving is for your considering this a reasonable
thing to try calculate for arc lengths, rather than the vector average
that minimises a different measure altogether.  Maybe MT also suggested
that as an alternative but I only remember his championing the vector
interpretation.  My apologies to MT if he did that as well.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16195

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

A couple of further thoughts only one of which is directed at you
Tim (at the end)...

Given the general conception of a mean (rather than any other kind of
summary statistic) as minimising the sum of squares of some "distance"
metric:

  Sum_{i=1,n} difference(A, t(i))^2

we can characterise the two contenders by what distance is being
minimised.  For the less well discussed "conventional average" (to use
your terminology) we are minimising the sum of squares of the shorter
arc lengths between A and the t(i).

For the "vector average", we convert the t(i) to unit vectors u(i) and
we calculate the mean if the u(i) to get a vector m.  The "average", A,
is just the direction of this vector -- another point on the unit
circle.  In this case we are minimising the sum of squares of the
/chord/ lengths between A and the t(i).

The mean vector itself (which may not lie on the unit circle) minimises
the sum of the squares of the length of the vector differences m-u(i):

  Sum_{i=1,n} |m - u(i)|^2

and any other vector along the same line as m (i.e. c*m for real c)
minimises

  Sum_{i=1,n} |c*m - u(i)|^2

This includes, of course, m projected out to the unit circle.

This distinction between arc lengths and chord lengths helps to
visualise where these averages differ, and why the conventional average
may seem more intuitive.

Incidentally, I found another book on statistics on spheres, and that
gets the average over in a few paragraphs.  It states, without
considering any alternatives, that the average is the vector average.  I
can't find anyone using or citing the arc-length minimising average,
despite it being natural on a sphere to find the mid-point of, say, a
set of points on the Earth's surface.

Tim, my best shot at calculating this other average sorts the points to
find the widest gap.  I suspect your algorithm is similar since you say
it is O(n log n).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16198

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
> A couple of further thoughts only one of which is directed at you
> Tim (at the end)...
>
> Given the general conception of a mean (rather than any other kind of
> summary statistic) as minimising the sum of squares of some "distance"
> metric:
>
>   Sum_{i=1,n} difference(A, t(i))^2
>
> we can characterise the two contenders by what distance is being
> minimised.  For the less well discussed "conventional average" (to use
> your terminology) we are minimising the sum of squares of the shorter
> arc lengths between A and the t(i).
>
> For the "vector average", we convert the t(i) to unit vectors u(i) and
> we calculate the mean if the u(i) to get a vector m.  The "average", A,
> is just the direction of this vector -- another point on the unit
> circle.  In this case we are minimising the sum of squares of the
> /chord/ lengths between A and the t(i).

I think of this approach differently.  I take the time values
t(i) as being unit masses on the unit circle, and calculate the
center of mass.  As long as the center of mass is not the origin
we can project it from the origin to find a corresponding time
value on the unit circle (which in my case is done implicitly by
using atan2()).

> The mean vector itself (which may not lie on the unit circle) minimises
> the sum of the squares of the length of the vector differences m-u(i):
>
>   Sum_{i=1,n} |m - u(i)|^2

That's true but I thought of it just as the average of the time
value "masses" on the unit circle.

> and any other vector along the same line as m (i.e. c*m for real c)
> minimises
>
>   Sum_{i=1,n} |c*m - u(i)|^2

I'm not sure what you're saying here.  Only the one point (m in
your terminology) minimizes the sum of squares of distances.  How
do other points on the same line qualify?

> This includes, of course, m projected out to the unit circle.
>
> This distinction between arc lengths and chord lengths helps to
> visualise where these averages differ, and why the conventional
> average may seem more intuitive.

Interesting perspective.  I wouldn't call them chord lengths
because I think of a chord as being between two points both on
the same circle, and the center of mass is never on the unit
circle (not counting the case when all the time values are the
same).  Even so it's an interesting way to view the distinction.

> Incidentally, I found another book on statistics on spheres, and that
> gets the average over in a few paragraphs.  It states, without
> considering any alternatives, that the average is the vector average.  I
> can't find anyone using or citing the arc-length minimising average,
> despite it being natural on a sphere to find the mid-point of, say, a
> set of points on the Earth's surface.

Do you mind my asking, which book was that?

Now that I think about it, finding the point that minimizes the
great circle distances squared would be at least computationally
unpleasant.  But it could be relevant in some contexts (thinking
in particular of astronautics, or, dare I say it, rocket science).

> Tim, my best shot at calculating this other average sorts the points to
> find the widest gap.  I suspect your algorithm is similar since you say
> it is O(n log n).

Your instinct that I sorted the time values is right.  If you
think a little more I think you will see that the widest gap need
not have any particular relationship to where the cut point is.
No further elaboration for now so as not to be a spoiler (and I
know you like to try figuring things out yourself).

[toc] | [prev] | [next] | [standalone]

#16199

On 2022-12-31 15:42, Tim Rentsch wrote:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

>> For the "vector average", we convert the t(i) to unit vectors u(i) and
>> we calculate the mean if the u(i) to get a vector m.  The "average", A,
>> is just the direction of this vector -- another point on the unit
>> circle.  In this case we are minimising the sum of squares of the
>> /chord/ lengths between A and the t(i).
> 
> I think of this approach differently.  I take the time values
> t(i) as being unit masses on the unit circle, and calculate the
> center of mass.  As long as the center of mass is not the origin
> we can project it from the origin to find a corresponding time
> value on the unit circle (which in my case is done implicitly by
> using atan2()).

Center of mass of a set of ideal points (particles) and vector average 
are same:

    CoM = Sum Mi * Ri / Sum Mi
          i = 1..n      i = 1..n

Mi = masses, Ri = vectors. If all Mi are same you get

    CoM = Sum Ri / n
          i = 1..n

>> This distinction between arc lengths and chord lengths helps to
>> visualise where these averages differ, and why the conventional
>> average may seem more intuitive.
> 
> Interesting perspective.  I wouldn't call them chord lengths
> because I think of a chord as being between two points both on
> the same circle, and the center of mass is never on the unit
> circle (not counting the case when all the time values are the
> same).  Even so it's an interesting way to view the distinction.

Arc length is proportional to angle:

    L = Rα, R is radius, α is angle in radians.

Averaging arcs is equivalent to averaging angles.

> Now that I think about it, finding the point that minimizes the
> great circle distances squared would be at least computationally
> unpleasant.

See above, it is just angles to average.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16205

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2022-12-31 15:42, Tim Rentsch wrote:
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>>> For the "vector average", we convert the t(i) to unit vectors u(i) and
>>> we calculate the mean if the u(i) to get a vector m.  The "average", A,
>>> is just the direction of this vector -- another point on the unit
>>> circle.  In this case we are minimising the sum of squares of the
>>> /chord/ lengths between A and the t(i).
>> I think of this approach differently.  I take the time values
>> t(i) as being unit masses on the unit circle, and calculate the
>> center of mass.  As long as the center of mass is not the origin
>> we can project it from the origin to find a corresponding time
>> value on the unit circle (which in my case is done implicitly by
>> using atan2()).
>
> Center of mass of a set of ideal points (particles) and vector average are same:
>
>    CoM = Sum Mi * Ri / Sum Mi
>          i = 1..n      i = 1..n
>
> Mi = masses, Ri = vectors. If all Mi are same you get
>
>    CoM = Sum Ri / n
>          i = 1..n
>
>>> This distinction between arc lengths and chord lengths helps to
>>> visualise where these averages differ, and why the conventional
>>> average may seem more intuitive.
>> Interesting perspective.  I wouldn't call them chord lengths
>> because I think of a chord as being between two points both on
>> the same circle, and the center of mass is never on the unit
>> circle (not counting the case when all the time values are the
>> same).  Even so it's an interesting way to view the distinction.
>
> Arc length is proportional to angle:
>
>    L = Rα, R is radius, α is angle in radians.
>
> Averaging arcs is equivalent to averaging angles.

Sure.  I'm certain Tim knows that!  The question is what "average" are
we interested in.  An average, angle A, minimises

  Sum_{i=1,n} distance(A, t(i))^2

for some measure of distance.  The most common circular (or spherical)
average, sums the unit vectors and, where possible, projects the
resultant vector onto the unit circle.  This average, it turns out,
minimises the sum of squares of the chords between A and the t(i).

Another average, which is more complicated to calculate, minimises the
sum of squares of the arc lengths or, as you say, the angular distances
between A and the t(i).

>> Now that I think about it, finding the point that minimizes the
>> great circle distances squared would be at least computationally
>> unpleasant.
>
> See above, it is just angles to average.

Yes, but that's hard.  The simple average (just sum the unit vectors)
does not minimise the sum of squares of the angle differences, and,
despite being a reasonable concept, is not discussed in any of the text
I've been able to find.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16266

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2022-12-31 15:42, Tim Rentsch wrote:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> For the "vector average", we convert the t(i) to unit vectors u(i) and
>>> we calculate the mean if the u(i) to get a vector m.  The "average", A,
>>> is just the direction of this vector -- another point on the unit
>>> circle.  In this case we are minimising the sum of squares of the
>>> /chord/ lengths between A and the t(i).
>>
>> I think of this approach differently.  I take the time values
>> t(i) as being unit masses on the unit circle, and calculate the
>> center of mass.  As long as the center of mass is not the origin
>> we can project it from the origin to find a corresponding time
>> value on the unit circle (which in my case is done implicitly by
>> using atan2()).
>
> Center of mass of a set of ideal points (particles) and vector
> average are same:

Yes, I thought the equivalence is obvious and not in need of
explanation.

>>> This distinction between arc lengths and chord lengths helps to
>>> visualise where these averages differ, and why the conventional
>>> average may seem more intuitive.
>>
>> Interesting perspective.  I wouldn't call them chord lengths
>> because I think of a chord as being between two points both on
>> the same circle, and the center of mass is never on the unit
>> circle (not counting the case when all the time values are the
>> same).  Even so it's an interesting way to view the distinction.
>
> Arc length is proportional to angle:

A trivial and useless observation.

> Averaging arcs is equivalent to averaging angles.

Angles are a one-dimensional measure.  Finding an arc length
"average" of points on a sphere needs a two-dimensional result.

>> Now that I think about it, finding the point that minimizes the
>> great circle distances squared would be at least computationally
>> unpleasant.
>
> See above, it is just angles to average.

Apparently you have not yet understood the problem.  Why don't
you try writing a program that inputs a set of points normalized
to be on the unit sphere, and then calculates the arc length
average point (on the unit sphere) of those input points?

[toc] | [prev] | [next] | [standalone]

#16267

On 2023-01-08 16:45, Tim Rentsch wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

>> Averaging arcs is equivalent to averaging angles.
> 
> Angles are a one-dimensional measure.

Averaging arcs is still equivalent to averaging angles, which is trivial 
result of elementary trigonometry.

> Finding an arc length
> "average" of points on a sphere needs a two-dimensional result.

Points do not have arcs.

>>> Now that I think about it, finding the point that minimizes the
>>> great circle distances squared would be at least computationally
>>> unpleasant.
>>
>> See above, it is just angles to average.
> 
> Apparently you have not yet understood the problem.

Again, averages of arcs and angles are equivalent up to a multiplier.

> Why don't
> you try writing a program that inputs a set of points normalized
> to be on the unit sphere, and then calculates the arc length
> average point (on the unit sphere) of those input points?

Why don't you write a formula specifying your need?

Programs are written according to the specifications. Numeric programs 
require a properly stated problem, rather than a bunch of words 
arbitrarily thrown in a meaningless sentence as above.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16272

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2023-01-08 16:45, Tim Rentsch wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>>> Averaging arcs is equivalent to averaging angles.
>> Angles are a one-dimensional measure.
>
> Averaging arcs is still equivalent to averaging angles, which is trivial result of elementary trigonometry.
>
>> Finding an arc length
>> "average" of points on a sphere needs a two-dimensional result.
>
> Points do not have arcs.
>
>>>> Now that I think about it, finding the point that minimizes the
>>>> great circle distances squared would be at least computationally
>>>> unpleasant.
>>>
>>> See above, it is just angles to average.
>> Apparently you have not yet understood the problem.
>
> Again, averages of arcs and angles are equivalent up to a multiplier.
>
>> Why don't
>> you try writing a program that inputs a set of points normalized
>> to be on the unit sphere, and then calculates the arc length
>> average point (on the unit sphere) of those input points?
>
> Why don't you write a formula specifying your need?

You seemed to understand the need sufficiently to dismiss the problem:
"averaging angles, which is trivial", "it is just angles to average" and
"averages of arcs and angles are equivalent up to a multiplier".  But
the problem is /finding/ a specific average -- the point (or angle) that
minimises the sum of squares of the distances (or angles) from that
average point (or angle).

The fact that it makes no odds (as everyone knows) whether we consider
angles (often called central angles in this context) or great circle
distances is not the issue.  It's finding the average that minimises the
sum of squares of differences that's the issue.

You say you need a formula, so I'll try...  Let P_n be a collection of n
unit vectors specifying n points on a unit sphere.  Find the unit vector
A that minimises

  Sum_{i=1,n} ( arctan( |A x P_n|  /  A . P_n ) )^2

(arctan is the "all quadrant" version that is often called atan2 in
programming languages.)

> Programs are written according to the specifications. Numeric programs
> require a properly stated problem, rather than a bunch of words
> arbitrarily thrown in a meaningless sentence as above.

Given the context, I think that's a very biased characterisation of
what's been said here.

My first job was as a "numerical analyst", and the very first program I
was employed to write was for a professor of statistics.  It was to
calculate a novel kind of fit line.  The specification was just a few
sentences.  No formulas.  It was perfectly clear, and I could get the
job done.  I don't think this is unusual.  Words are often enough, and
they can avoid undue over specification.  For example, the problem in
question is essentially the same if the points are given by latitude and
longitude on a non-unit sphere, but the formula would look very
different.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16273

On 08/01/2023 8:41 pm, Ben Bacarisse wrote:
> The specification was just a few
> sentences.

There hangs on the wall of $COMPANY$ (a UK insurance company) a 
restaurant's paper napkin in a wooden frame behind glass. 
Scribbled on the napkin in biro are the words "quotes system".

End of spec.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#16274

On 2023-01-08 21:41, Ben Bacarisse wrote:

> But
> the problem is /finding/ a specific average -- the point (or angle) that
> minimises the sum of squares of the distances (or angles) from that
> average point (or angle).

That is not a programming problem. It is a problem space's one. You must 
go to the corresponding part of science or engineering or economics etc 
and formulate it there in terms of that space.

Average is just such formulation of finding a representative member from 
some set having some specific properties. E.g. least squares in physics 
usually has the meaning of least energy etc. So, it goes in this order 
(not in reverse):

1. You need the least energy representative.
2. An average gives you that.
3. You measure the inputs.

After that you ask yourself given these measures how to compute the 
average? And only now it becomes a programming issue.

> The fact that it makes no odds (as everyone knows) whether we consider
> angles (often called central angles in this context) or great circle
> distances is not the issue.  It's finding the average that minimises the
> sum of squares of differences that's the issue.

Minimum of squares (Euclidean norm) is represented by the mathematical mean.

> You say you need a formula, so I'll try...  Let P_n be a collection of n
> unit vectors specifying n points on a unit sphere.  Find the unit vector
> A that minimises
> 
>    Sum_{i=1,n} ( arctan( |A x P_n|  /  A . P_n ) )^2
> 
> (arctan is the "all quadrant" version that is often called atan2 in
> programming languages.)

1. atan2 has two arguments (the adjacent and the opposite legs);
2. What is "A";
3. What operations(?) "x" and "." denote?

>> Programs are written according to the specifications. Numeric programs
>> require a properly stated problem, rather than a bunch of words
>> arbitrarily thrown in a meaningless sentence as above.
> 
> Given the context, I think that's a very biased characterisation of
> what's been said here.
> 
> My first job was as a "numerical analyst", and the very first program I
> was employed to write was for a professor of statistics.  It was to
> calculate a novel kind of fit line.  The specification was just a few
> sentences.  No formulas.  It was perfectly clear, and I could get the
> job done.  I don't think this is unusual.  Words are often enough, and
> they can avoid undue over specification.  For example, the problem in
> question is essentially the same if the points are given by latitude and
> longitude on a non-unit sphere, but the formula would look very
> different.

This just means that you formulated the specifications yourself, being 
able to read your professor's mind. Not everybody's mind is easy read or 
worth reading... (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16276

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2023-01-08 21:41, Ben Bacarisse wrote:
>
>> But
>> the problem is /finding/ a specific average -- the point (or angle) that
>> minimises the sum of squares of the distances (or angles) from that
>> average point (or angle).
>
> That is not a programming problem. It is a problem space's one. You
> must go to the corresponding part of science or engineering or
> economics etc and formulate it there in terms of that space.

I don't follow.  It's a mathematical problem for which an algorithm is
sought.  I don't see any connection to some science or engineering
space.  If it /came/ from some scientific study, it has already been
turned into what the programmer needs come up with.

> Average is just such formulation of finding a representative member
> from some set having some specific properties. E.g. least squares in
> physics usually has the meaning of least energy etc. So, it goes in
> this order (not in reverse):
>
> 1. You need the least energy representative.
> 2. An average gives you that.
> 3. You measure the inputs.
>
> After that you ask yourself given these measures how to compute the
> average? And only now it becomes a programming issue.

So if I asked you for code to calculate the arithmetic mean of an array
of numbers you would ask for all this first, declaring it not yet a
programming issue?  I really don't see where all this comes from.

>> The fact that it makes no odds (as everyone knows) whether we consider
>> angles (often called central angles in this context) or great circle
>> distances is not the issue.  It's finding the average that minimises the
>> sum of squares of differences that's the issue.
>
> Minimum of squares (Euclidean norm) is represented by the mathematical
> mean.

This problem obviously uses a different norm.

>> You say you need a formula, so I'll try...  Let P_n be a collection of n
>> unit vectors specifying n points on a unit sphere.  Find the unit vector
>> A that minimises
>>    Sum_{i=1,n} ( arctan( |A x P_n|  /  A . P_n ) )^2
>> (arctan is the "all quadrant" version that is often called atan2 in
>> programming languages.)
>
> 1. atan2 has two arguments (the adjacent and the opposite legs);

Obviously I can't guess how much I can safely assume so I expected there
might be questions.  arctan(p / q) is usually coded as atan2(p, q).

> 2. What is "A";

The unit vector that is being sought -- the result of the algorithm.  It
represents a point on the unit sphere that is the desired average of the
input points.

> 3. What operations(?) "x" and "." denote?

x denotes the cross product, and . the dot product.

Do you agree that this is not a trivial problem?  If not, please give
the trivial algorithm!

>>> Programs are written according to the specifications. Numeric programs
>>> require a properly stated problem, rather than a bunch of words
>>> arbitrarily thrown in a meaningless sentence as above.
>> Given the context, I think that's a very biased characterisation of
>> what's been said here.
>> My first job was as a "numerical analyst", and the very first program I
>> was employed to write was for a professor of statistics.  It was to
>> calculate a novel kind of fit line.  The specification was just a few
>> sentences.  No formulas.  It was perfectly clear, and I could get the
>> job done.  I don't think this is unusual.  Words are often enough, and
>> they can avoid undue over specification.  For example, the problem in
>> question is essentially the same if the points are given by latitude and
>> longitude on a non-unit sphere, but the formula would look very
>> different.
>
> This just means that you formulated the specifications yourself, being
> able to read your professor's mind.

No, I did not have to read his mind because he told me what he wanted.
To my mind "find the point on the sphere that minimises the sum of the
squares of the great-circle distances between that point and the input
points" is clearer than the formula I gave because the formula says too
much.

Of course, no specification is 100% precise.  You didn't know what x and
. denoted above and I have answered you with mere words.  Will you need
the formulas for X x Y and X . Y before accepting the specification?
What symbols in /those/ formulas might you want to have formally
specified?

> Not everybody's mind is easy read or worth reading... (:-))

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16277

On 2023-01-09 04:25, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 2023-01-08 21:41, Ben Bacarisse wrote:
>>
>>> But
>>> the problem is /finding/ a specific average -- the point (or angle) that
>>> minimises the sum of squares of the distances (or angles) from that
>>> average point (or angle).
>>
>> That is not a programming problem. It is a problem space's one. You
>> must go to the corresponding part of science or engineering or
>> economics etc and formulate it there in terms of that space.
> 
> I don't follow.  It's a mathematical problem for which an algorithm is
> sought.

Firstly, this is comp.programming group. Secondly, if algorithm is 
sought then there must be a mathematical formulation of what a numeric 
solution is sought for.

(Finding a minimum is an optimization problem, there are thousands of 
algorithms already)

> I don't see any connection to some science or engineering
> space.  If it /came/ from some scientific study, it has already been
> turned into what the programmer needs come up with.
> 
>> Average is just such formulation of finding a representative member
>> from some set having some specific properties. E.g. least squares in
>> physics usually has the meaning of least energy etc. So, it goes in
>> this order (not in reverse):
>>
>> 1. You need the least energy representative.
>> 2. An average gives you that.
>> 3. You measure the inputs.
>>
>> After that you ask yourself given these measures how to compute the
>> average? And only now it becomes a programming issue.
> 
> So if I asked you for code to calculate the arithmetic mean of an array
> of numbers you would ask for all this first, declaring it not yet a
> programming issue?

Then I would ask you, if this is a solution, what was the problem?

> I really don't see where all this comes from.

 From an average (:-)) customer who does not mind his business. 
Customers have programming ideas, wrong ideas, ideas they express in 
terms they have no idea of (:-)). It takes time and tact to bring the 
customer back to the field of his expertise and get from him what he 
actually needs in order to solve his actual problem.

>>> The fact that it makes no odds (as everyone knows) whether we consider
>>> angles (often called central angles in this context) or great circle
>>> distances is not the issue.  It's finding the average that minimises the
>>> sum of squares of differences that's the issue.
>>
>> Minimum of squares (Euclidean norm) is represented by the mathematical
>> mean.
> 
> This problem obviously uses a different norm.

I see nothing obvious in an unstated problem.

>>> You say you need a formula, so I'll try...  Let P_n be a collection of n
>>> unit vectors specifying n points on a unit sphere.  Find the unit vector
>>> A that minimises
>>>     Sum_{i=1,n} ( arctan( |A x P_n|  /  A . P_n ) )^2
>>> (arctan is the "all quadrant" version that is often called atan2 in
>>> programming languages.)
>>
>> 1. atan2 has two arguments (the adjacent and the opposite legs);
> 
> Obviously I can't guess how much I can safely assume so I expected there
> might be questions.  arctan(p / q) is usually coded as atan2(p, q).
> 
>> 2. What is "A";
> 
> The unit vector that is being sought -- the result of the algorithm.  It
> represents a point on the unit sphere that is the desired average of the
> input points.
> 
>> 3. What operations(?) "x" and "." denote?
> 
> x denotes the cross product, and . the dot product.
> 
> Do you agree that this is not a trivial problem?  If not, please give
> the trivial algorithm!

If I correctly understood your explanation (and with a few obvious 
corrections):

    Sum atan2 (|A x Pi|, A · Pi)  --> min
   i=1..n                       {A | A on the circle}

|A x Pi| = |A| |Pi| |sin θi|  (θi is the angle between the vectors A and Pi)

A · Pi = |A| |Pi| cos θi

atan2 (|A x Pi|, A · Pi) = atan2 (|sin θi|, cos θi) = θi'

Where θi' is θi with lower semicircle mapped to the upper one (for 
whatever reason).

(If mapping was unintended you must have taken the direction of the 
cross product for the sign for |A x Pi|)

On a circle varying the angle between A and (R, 0), where R is the 
radius, you find that the mean of the angles between Pi and (R, 0) 
yields the minimum.

> To my mind "find the point on the sphere that minimises the sum of the
> squares of the great-circle distances between that point and the input
> points" is clearer than the formula I gave because the formula says too
> much.

If you mean the circumference, then that is trivially proportional to 
the angle.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16279

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2023-01-09 04:25, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>> 
>>> On 2023-01-08 21:41, Ben Bacarisse wrote:
>>>
>>>> But
>>>> the problem is /finding/ a specific average -- the point (or angle) that
>>>> minimises the sum of squares of the distances (or angles) from that
>>>> average point (or angle).
>>>
>>> That is not a programming problem. It is a problem space's one. You
>>> must go to the corresponding part of science or engineering or
>>> economics etc and formulate it there in terms of that space.
>> I don't follow.  It's a mathematical problem for which an algorithm is
>> sought.
>
> Firstly, this is comp.programming group.

Do you consider discussion algorithms off topic here?  Seriously?

> Secondly, if algorithm is sought then there must be a mathematical
> formulation of what a numeric solution is sought for.

There needs to be a problem statement that can be discussed and refined.
The original post about circular averages has led to two different
refinements -- the vector average (projected onto the unit circle) and
the arc-length average.  Both generalise to more dimensions and I
happened to mention in passing that the great-circle average would be a
natural fit in some situations.

Tim mentioned (again in passing) that it looks hard.  You seemed to
suggest it was not, but I am not sure you knew what the problem was at
that time.

All of this seems to be to be exactly what comp.programming should be
about.

> (Finding a minimum is an optimization problem, there are thousands of
> algorithms already)

Programmers should know that specifications are not algorithm designs.
You would not find a number that minimises the sum of squares of
differences from an input set by breaking out one of these thousands of
minimisation algorithms.  You'd sum and divide.

>> I don't see any connection to some science or engineering
>> space.  If it /came/ from some scientific study, it has already been
>> turned into what the programmer needs come up with.
>> 
>>> Average is just such formulation of finding a representative member
>>> from some set having some specific properties. E.g. least squares in
>>> physics usually has the meaning of least energy etc. So, it goes in
>>> this order (not in reverse):
>>>
>>> 1. You need the least energy representative.
>>> 2. An average gives you that.
>>> 3. You measure the inputs.
>>>
>>> After that you ask yourself given these measures how to compute the
>>> average? And only now it becomes a programming issue.
>> So if I asked you for code to calculate the arithmetic mean of an array
>> of numbers you would ask for all this first, declaring it not yet a
>> programming issue?
>
> Then I would ask you, if this is a solution, what was the problem?

This is a solution to the simpler problem.

>> I really don't see where all this comes from.
>
> From an average (:-)) customer who does not mind his
> business. Customers have programming ideas, wrong ideas, ideas they
> express in terms they have no idea of (:-)). It takes time and tact to
> bring the customer back to the field of his expertise and get from him
> what he actually needs in order to solve his actual problem.

But we are not in that situation.  A few knowledgeable and experienced
people are discussing a programming problem.  You are welcome to join
in, but the best way for you to do that is to ask whatever questions you
think would help you understand what's being discussed.  So far, your
replies have alternated between "it's trivial" and "it's unstated".

>>>> The fact that it makes no odds (as everyone knows) whether we consider
>>>> angles (often called central angles in this context) or great circle
>>>> distances is not the issue.  It's finding the average that minimises the
>>>> sum of squares of differences that's the issue.
>>>
>>> Minimum of squares (Euclidean norm) is represented by the mathematical
>>> mean.
>> This problem obviously uses a different norm.
>
> I see nothing obvious in an unstated problem.

It's been stated several times.

>>>> You say you need a formula, so I'll try...  Let P_n be a collection of n
>>>> unit vectors specifying n points on a unit sphere.  Find the unit vector
>>>> A that minimises
>>>>     Sum_{i=1,n} ( arctan( |A x P_n|  /  A . P_n ) )^2
>>>> (arctan is the "all quadrant" version that is often called atan2 in
>>>> programming languages.)
>>>
>>> 1. atan2 has two arguments (the adjacent and the opposite legs);
>> Obviously I can't guess how much I can safely assume so I expected there
>> might be questions.  arctan(p / q) is usually coded as atan2(p, q).
>> 
>>> 2. What is "A";
>> The unit vector that is being sought -- the result of the algorithm.  It
>> represents a point on the unit sphere that is the desired average of the
>> input points.
>> 
>>> 3. What operations(?) "x" and "." denote?
>> x denotes the cross product, and . the dot product.
>> Do you agree that this is not a trivial problem?  If not, please give
>> the trivial algorithm!
>
> If I correctly understood your explanation (and with a few obvious
> corrections):
>
>    Sum atan2 (|A x Pi|, A · Pi)  --> min
>   i=1..n                       {A | A on the circle}

No.  A is a vector denoting a point on the unit sphere.  And you have
missed out the power of two.  Were these changes what you call "obvious
corrections"?

> |A x Pi| = |A| |Pi| |sin θi|  (θi is the angle between the vectors A and Pi)
>
> A · Pi = |A| |Pi| cos θi
>
> atan2 (|A x Pi|, A · Pi) = atan2 (|sin θi|, cos θi) = θi'
>
> Where θi' is θi with lower semicircle mapped to the upper one (for
> whatever reason).
>
> (If mapping was unintended you must have taken the direction of the
> cross product for the sign for |A x Pi|)
>
> On a circle varying the angle between A and (R, 0), where R is the
> radius, you find that the mean of the angles between Pi and (R, 0)
> yields the minimum.

This does not even solve the related case of finding the average point
on the unit circle.

>> To my mind "find the point on the sphere that minimises the sum of the
>> squares of the great-circle distances between that point and the input
>> points" is clearer than the formula I gave because the formula says too
>> much.
>
> If you mean the circumference, then that is trivially proportional to
> the angle.

You keep making the point that angles are proportional to arcs and/or
great circle distances.  No one disputes this and I even tried at one
point to keep writing both so you would know that that is not the issue.
The problem is finding the average.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16283

On 2023-01-09 21:37, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 2023-01-09 04:25, Ben Bacarisse wrote:
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>
>>>> On 2023-01-08 21:41, Ben Bacarisse wrote:
>>>>
>>>>> But
>>>>> the problem is /finding/ a specific average -- the point (or angle) that
>>>>> minimises the sum of squares of the distances (or angles) from that
>>>>> average point (or angle).
>>>>
>>>> That is not a programming problem. It is a problem space's one. You
>>>> must go to the corresponding part of science or engineering or
>>>> economics etc and formulate it there in terms of that space.
>>> I don't follow.  It's a mathematical problem for which an algorithm is
>>> sought.
>>
>> Firstly, this is comp.programming group.
> 
> Do you consider discussion algorithms off topic here?  Seriously?

No, I consider off topic discussing mathematical problems /= algorithms. 
You did not discuss any algorithms so far.

>> Secondly, if algorithm is sought then there must be a mathematical
>> formulation of what a numeric solution is sought for.
> 
> There needs to be a problem statement that can be discussed and refined.
> The original post about circular averages has led to two different
> refinements -- the vector average (projected onto the unit circle) and
> the arc-length average.  Both generalise to more dimensions and I
> happened to mention in passing that the great-circle average would be a
> natural fit in some situations.

I missed generalization to 3D. Sorry.
[You kept on writing about unit *circle* and an angle, where it actually 
meant unit sphere and polar angles/spherical coordinates]

> Tim mentioned (again in passing) that it looks hard.  You seemed to
> suggest it was not, but I am not sure you knew what the problem was at
> that time.
> 
> All of this seems to be to be exactly what comp.programming should be
> about.

Differential geometry and spherical trigonometry are certainly off topic.

>> (Finding a minimum is an optimization problem, there are thousands of
>> algorithms already)
> 
> Programmers should know that specifications are not algorithm designs.

Who said they are?

>>> I don't see any connection to some science or engineering
>>> space.  If it /came/ from some scientific study, it has already been
>>> turned into what the programmer needs come up with.
>>>
>>>> Average is just such formulation of finding a representative member
>>>> from some set having some specific properties. E.g. least squares in
>>>> physics usually has the meaning of least energy etc. So, it goes in
>>>> this order (not in reverse):
>>>>
>>>> 1. You need the least energy representative.
>>>> 2. An average gives you that.
>>>> 3. You measure the inputs.
>>>>
>>>> After that you ask yourself given these measures how to compute the
>>>> average? And only now it becomes a programming issue.
>>> So if I asked you for code to calculate the arithmetic mean of an array
>>> of numbers you would ask for all this first, declaring it not yet a
>>> programming issue?
>>
>> Then I would ask you, if this is a solution, what was the problem?
> 
> This is a solution to the simpler problem.

And what was that the problem? [Adjective adds/clarifies nothing]

> But we are not in that situation.  A few knowledgeable and experienced
> people are discussing a programming problem.

I saw no discussion on programming so either.

> You are welcome to join
> in, but the best way for you to do that is to ask whatever questions you
> think would help you understand what's being discussed.  So far, your
> replies have alternated between "it's trivial" and "it's unstated".

Yes, because you wrote about minimum of arc length on a *circle*. And 
that is trivial.

>>>>> You say you need a formula, so I'll try...  Let P_n be a collection of n
>>>>> unit vectors specifying n points on a unit sphere.  Find the unit vector
>>>>> A that minimises
>>>>>      Sum_{i=1,n} ( arctan( |A x P_n|  /  A . P_n ) )^2
>>>>> (arctan is the "all quadrant" version that is often called atan2 in
>>>>> programming languages.)
>>>>
>>>> 1. atan2 has two arguments (the adjacent and the opposite legs);
>>> Obviously I can't guess how much I can safely assume so I expected there
>>> might be questions.  arctan(p / q) is usually coded as atan2(p, q).
>>>
>>>> 2. What is "A";
>>> The unit vector that is being sought -- the result of the algorithm.  It
>>> represents a point on the unit sphere that is the desired average of the
>>> input points.
>>>
>>>> 3. What operations(?) "x" and "." denote?
>>> x denotes the cross product, and . the dot product.
>>> Do you agree that this is not a trivial problem?  If not, please give
>>> the trivial algorithm!
>>
>> If I correctly understood your explanation (and with a few obvious
>> corrections):
>>
>>     Sum atan2 (|A x Pi|, A · Pi)  --> min
>>    i=1..n                       {A | A on the circle}
> 
> No.  A is a vector denoting a point on the unit sphere.  And you have
> missed out the power of two.  Were these changes what you call "obvious
> corrections"?
> 
>> |A x Pi| = |A| |Pi| |sin θi|  (θi is the angle between the vectors A and Pi)
>>
>> A · Pi = |A| |Pi| cos θi
>>
>> atan2 (|A x Pi|, A · Pi) = atan2 (|sin θi|, cos θi) = θi'
>>
>> Where θi' is θi with lower semicircle mapped to the upper one (for
>> whatever reason).
>>
>> (If mapping was unintended you must have taken the direction of the
>> cross product for the sign for |A x Pi|)
>>
>> On a circle varying the angle between A and (R, 0), where R is the
>> radius, you find that the mean of the angles between Pi and (R, 0)
>> yields the minimum.
> 
> This does not even solve the related case of finding the average point
> on the unit circle.

It elementary does for both formula you gave (after corrections) and the 
circumference:

    Sum Length_Of_Arc (Pi, A)^2 =
   i=1..n

=  Sum (R Angle (Pi, A))^2 =
   i=1..n

=  R^2 Sum ((Angle (Pi, (R, 0)) - Angle (A, (R, 0)))^2
       i=1..n

(R, 0) denotes vector x = R, y = 0. Let θi denote Angle (Pi, (R, 0)) and 
α do Angle (A, (R, 0)) then

=  R^2 Sum (θi - α)^2 --> min
       i=1..n

Derivative d/dα:

   2 R^2 Sum (θi - α) = 0 <=> (R /= 0)
        i=1..n

<=> Sum θi - nα = 0 <=>
    i=1..n

<=> α = Sum θi / n = mean ({θi})
        i=1..n

The angle between A and (R, 0) is the mean of angles of points.

I can't help you with spherical trigonometry, which is an utter off 
topic anyway. I do not know if there is a direct solution of least 
squares. For two points it is like for a circle. For three points it 
would be the circumcenter of the spherical triangle.

However even if the direct solution existed, it could be numerically 
unstable as many formulae in spherical geometry are. I used to process 
remote sensing geological data which involved miles long chains of 
cosines and sines. That stuff was no fun.

Anyway, there are lengthy papers on spherical averages introducing 
iterative solutions, some with source code for the algorithms. That is 
the right way to compute it, if you really wanted...

[Again, it is not programming. In case of spherical geometry a 
programmer will find an expert mathematician and who will have the 
problem properly stated. The next stop is by an expert applied 
mathematician who will outline a workable numeric solution. Then the 
programmer can start.]

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16286

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2023-01-09 21:37, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>> 
>>> On 2023-01-09 04:25, Ben Bacarisse wrote:
>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>>
>>>>> On 2023-01-08 21:41, Ben Bacarisse wrote:
>>>>>
>>>>>> But
>>>>>> the problem is /finding/ a specific average -- the point (or angle) that
>>>>>> minimises the sum of squares of the distances (or angles) from that
>>>>>> average point (or angle).
>>>>>
>>>>> That is not a programming problem. It is a problem space's one. You
>>>>> must go to the corresponding part of science or engineering or
>>>>> economics etc and formulate it there in terms of that space.
>>>> I don't follow.  It's a mathematical problem for which an algorithm is
>>>> sought.
>>>
>>> Firstly, this is comp.programming group.
>> Do you consider discussion algorithms off topic here?  Seriously?
>
> No, I consider off topic discussing mathematical problems /=
> algorithms. You did not discuss any algorithms so far.

Algorithms don't come out of thin air.  The objective must be discussed
first.  You can't seriously think that everyone here should remain
silent until, out of nowhere, someone says "consider this algorithm to
find the average of a set of points".

>>> Secondly, if algorithm is sought then there must be a mathematical
>>> formulation of what a numeric solution is sought for.
>> There needs to be a problem statement that can be discussed and refined.
>> The original post about circular averages has led to two different
>> refinements -- the vector average (projected onto the unit circle) and
>> the arc-length average.  Both generalise to more dimensions and I
>> happened to mention in passing that the great-circle average would be a
>> natural fit in some situations.
>
> I missed generalization to 3D. Sorry.
> [You kept on writing about unit *circle* and an angle, where it
> actually meant unit sphere and polar angles/spherical coordinates]

Both have been discussed, but I think I've been clear about which one I
am talking about.

>> Tim mentioned (again in passing) that it looks hard.  You seemed to
>> suggest it was not, but I am not sure you knew what the problem was at
>> that time.
>> All of this seems to be to be exactly what comp.programming should be
>> about.
>
> Differential geometry and spherical trigonometry are certainly off
> topic.

I don't think I discussed either.

>>> (Finding a minimum is an optimization problem, there are thousands of
>>> algorithms already)
>> Programmers should know that specifications are not algorithm designs.
>
> Who said they are?

I explained in the text you cut.  Maybe your reference to the thousands
of minimisation algorithms was just an off the cuff remark, but it reads
as if you were suggesting using one as them as the solution to this
programming task.

>>>> I don't see any connection to some science or engineering
>>>> space.  If it /came/ from some scientific study, it has already been
>>>> turned into what the programmer needs come up with.
>>>>
>>>>> Average is just such formulation of finding a representative member
>>>>> from some set having some specific properties. E.g. least squares in
>>>>> physics usually has the meaning of least energy etc. So, it goes in
>>>>> this order (not in reverse):
>>>>>
>>>>> 1. You need the least energy representative.
>>>>> 2. An average gives you that.
>>>>> 3. You measure the inputs.
>>>>>
>>>>> After that you ask yourself given these measures how to compute the
>>>>> average? And only now it becomes a programming issue.
>>>> So if I asked you for code to calculate the arithmetic mean of an array
>>>> of numbers you would ask for all this first, declaring it not yet a
>>>> programming issue?
>>>
>>> Then I would ask you, if this is a solution, what was the problem?
>> This is a solution to the simpler problem.
>
> And what was that the problem? [Adjective adds/clarifies nothing]
>
>> But we are not in that situation.  A few knowledgeable and experienced
>> people are discussing a programming problem.
>
> I saw no discussion on programming so either.
>
>> You are welcome to join
>> in, but the best way for you to do that is to ask whatever questions you
>> think would help you understand what's being discussed.  So far, your
>> replies have alternated between "it's trivial" and "it's unstated".
>
> Yes, because you wrote about minimum of arc length on a *circle*. And
> that is trivial.

I think I have been clear that the problem you claimed was trivial was
about points on a sphere.

But the circle version is not trivial in the sense you seem to think it
is.  What you say below about seems to miss the key issue altogether.

>>>>>> You say you need a formula, so I'll try...  Let P_n be a collection of n
>>>>>> unit vectors specifying n points on a unit sphere.  Find the unit vector
>>>>>> A that minimises
>>>>>>      Sum_{i=1,n} ( arctan( |A x P_n|  /  A . P_n ) )^2
>>>>>> (arctan is the "all quadrant" version that is often called atan2 in
>>>>>> programming languages.)
>>>>>
>>>>> 1. atan2 has two arguments (the adjacent and the opposite legs);
>>>> Obviously I can't guess how much I can safely assume so I expected there
>>>> might be questions.  arctan(p / q) is usually coded as atan2(p, q).
>>>>
>>>>> 2. What is "A";
>>>> The unit vector that is being sought -- the result of the algorithm.  It
>>>> represents a point on the unit sphere that is the desired average of the
>>>> input points.
>>>>
>>>>> 3. What operations(?) "x" and "." denote?
>>>> x denotes the cross product, and . the dot product.
>>>> Do you agree that this is not a trivial problem?  If not, please give
>>>> the trivial algorithm!
>>>
>>> If I correctly understood your explanation (and with a few obvious
>>> corrections):
>>>
>>>     Sum atan2 (|A x Pi|, A · Pi)  --> min
>>>    i=1..n                       {A | A on the circle}
>> No.  A is a vector denoting a point on the unit sphere.  And you have
>> missed out the power of two.  Were these changes what you call "obvious
>> corrections"?
>> 
>>> |A x Pi| = |A| |Pi| |sin θi|  (θi is the angle between the vectors A and Pi)
>>>
>>> A · Pi = |A| |Pi| cos θi
>>>
>>> atan2 (|A x Pi|, A · Pi) = atan2 (|sin θi|, cos θi) = θi'
>>>
>>> Where θi' is θi with lower semicircle mapped to the upper one (for
>>> whatever reason).
>>>
>>> (If mapping was unintended you must have taken the direction of the
>>> cross product for the sign for |A x Pi|)
>>>
>>> On a circle varying the angle between A and (R, 0), where R is the
>>> radius, you find that the mean of the angles between Pi and (R, 0)
>>> yields the minimum.
>> This does not even solve the related case of finding the average point
>> on the unit circle.
>
> It elementary does for both formula you gave (after corrections) and
> the circumference:
>
>    Sum Length_Of_Arc (Pi, A)^2 =
>   i=1..n
>
> =  Sum (R Angle (Pi, A))^2 =
>   i=1..n
>
> =  R^2 Sum ((Angle (Pi, (R, 0)) - Angle (A, (R, 0)))^2
>       i=1..n

There's no need to bring R into it.  Either accept that this is a unit
circle or consider only the angles.

> (R, 0) denotes vector x = R, y = 0. Let θi denote Angle (Pi, (R, 0))
> and α do Angle (A, (R, 0)) then

Simpler to start from here -- to find the average of the angles -- the
angle that minimises the sum of squares of angular differences:

> =  R^2 Sum (θi - α)^2 --> min
>       i=1..n
>
> Derivative d/dα:
>
>   2 R^2 Sum (θi - α) = 0 <=> (R /= 0)
>        i=1..n
>
> <=> Sum θi - nα = 0 <=>
>    i=1..n
>
> <=> α = Sum θi / n = mean ({θi})
>        i=1..n
>
> The angle between A and (R, 0) is the mean of angles of points.

I don't think you have grasped the basic problem.  If you want to
consider the circular case you'll have to review the posts that were
specifically about it.  You seem to be suggesting that a conventional
mean solves the problem.

> Anyway, there are lengthy papers on spherical averages introducing
> iterative solutions, some with source code for the algorithms. That is
> the right way to compute it, if you really wanted...

I'd like to read one.  Do you have a citation, please?  The only
treatments I've found don't discuss the average that Tim and I were
talking about.  They only consider the simple vector average.  (But I've
only found two.)

> [Again, it is not programming. In case of spherical geometry a
> programmer will find an expert mathematician and who will have the
> problem properly stated.

The problem has been properly stated.  We seek an algorithm that finds a
point that minimises the sum of squares of the great-circle distances
between that point and the input points.  You could have asked if any of
this was unclear.  To me it is both clear and intuitive.

> The next stop is by an expert applied mathematician who will outline a
> workable numeric solution. Then the programmer can start.]

Ah, you hand off the task of devising algorithms to mathematicians?
That would make programming very dull.  Anyway, you would not tackle
this sort of problem until an expert applied mathematician has done
everything except code up a workable numerical solution.  Is that also
the case for the average angle problem?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16289

On 2023-01-11 03:41, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 2023-01-09 21:37, Ben Bacarisse wrote:
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>
>>>> On 2023-01-09 04:25, Ben Bacarisse wrote:
>>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>>>
>>>> Firstly, this is comp.programming group.
>>> Do you consider discussion algorithms off topic here?  Seriously?
>>
>> No, I consider off topic discussing mathematical problems /=
>> algorithms. You did not discuss any algorithms so far.
> 
> Algorithms don't come out of thin air.  The objective must be discussed
> first.  You can't seriously think that everyone here should remain
> silent until, out of nowhere, someone says "consider this algorithm to
> find the average of a set of points".

> I explained in the text you cut.  Maybe your reference to the thousands
> of minimisation algorithms was just an off the cuff remark, but it reads
> as if you were suggesting using one as them as the solution to this
> programming task.

Sure. I highly doubt that production code, if ever existed, would use 
some novel algorithm.

>> Anyway, there are lengthy papers on spherical averages introducing
>> iterative solutions, some with source code for the algorithms. That is
>> the right way to compute it, if you really wanted...
> 
> I'd like to read one.  Do you have a citation, please?

Perhaps this could be a starting point:

"Spherical Averages and Applications to Spherical Splines and 
Interpolation" Samuel R. Buss, Jay P. Fillmore

It is not area of my interest and research is not a programming task 
either. And you still completely miss the key point about stating the 
problem. The problems come from the problem spaces. Spherical geometry 
is used in remote sensing, navigation, computer graphics (spherical 
polygons and triangles) etc. You must look for works in these 
application areas first. If the problem were *real* you would already 
have that step behind.

>> [Again, it is not programming. In case of spherical geometry a
>> programmer will find an expert mathematician and who will have the
>> problem properly stated.
> 
> The problem has been properly stated.  We seek an algorithm that finds a
> point that minimises the sum of squares of the great-circle distances
> between that point and the input points.  You could have asked if any of
> this was unclear.  To me it is both clear and intuitive.
> 
>> The next stop is by an expert applied mathematician who will outline a
>> workable numeric solution. Then the programmer can start.]
> 
> Ah, you hand off the task of devising algorithms to mathematicians?

Yep, *numeric* algorithms is an area of applied mathematics.

> That would make programming very dull.  Anyway, you would not tackle
> this sort of problem until an expert applied mathematician has done
> everything except code up a workable numerical solution.  Is that also
> the case for the average angle problem?

If you are not familiar with spherical geometry, numerical approximation 
and optimization, yes.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16294

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2023-01-11 03:41, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

>>> Anyway, there are lengthy papers on spherical averages introducing
>>> iterative solutions, some with source code for the algorithms. That is
>>> the right way to compute it, if you really wanted...
>
>> I'd like to read one.  Do you have a citation, please?
>
> Perhaps this could be a starting point:
>
> "Spherical Averages and Applications to Spherical Splines and
> Interpolation" Samuel R. Buss, Jay P. Fillmore

Thanks.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16288

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2023-01-08 16:45, Tim Rentsch wrote:
>
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>
>>> Averaging arcs is equivalent to averaging angles.
>>
>> Angles are a one-dimensional measure.
>
> Averaging arcs is still equivalent to averaging angles, which is
> trivial result of elementary trigonometry.
>
>> Finding an arc length
>> "average" of points on a sphere needs a two-dimensional result.
>
> Points do not have arcs.
>
>>>> Now that I think about it, finding the point that minimizes the
>>>> great circle distances squared would be at least computationally
>>>> unpleasant.
>>>
>>> See above, it is just angles to average.
>>
>> Apparently you have not yet understood the problem.
>
> Again, averages of arcs and angles are equivalent up to a
> multiplier.
>
>> Why don't
>> you try writing a program that inputs a set of points normalized
>> to be on the unit sphere, and then calculates the arc length
>> average point (on the unit sphere) of those input points?
>
> Why don't you write a formula specifying your need?
>
> Programs are written according to the specifications.  Numeric
> programs require a properly stated problem, rather than a bunch
> of words arbitrarily thrown in a meaningless sentence as above.

After reading this response and also three other responses of
yours (to Ben Bacarisse) down stream, I can't help but think you
have little or no interest in understanding the problem, offering
any useful comments about it, or trying to write a program to
solve the problem.  Apparently the only interest you do have is
making captious remarks.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming

csiph-web