"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?

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

"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.

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

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

"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.

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

"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.

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

"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.

"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.

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

"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.