From: ben.usenet@bsb.me.uk   
      
   "Dmitry A. Kazakov"  writes:   
      
   > On 2023-01-09 04:25, Ben Bacarisse wrote:   
   >> "Dmitry A. Kazakov"  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.   
      
   [continued in next message]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)