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

Groups > comp.programming > #16277

Re: Another little puzzle

Show all headers | View raw

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

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