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

Groups > comp.programming > #16279

Re: Another little puzzle

Show key headers only | View raw

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

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

Thread

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

csiph-web