Description. Geometric Medians on a Sphere.
- Author:
- Roman Chijner
- Topic:
- Algebra, Calculus, Circle, Difference and Slope, Differential Calculus, Differential Equation, Equations, Optimization Problems, Functions, Geometry, Function Graph, Intersection, Linear Functions, Linear Programming or Linear Optimization, Mathematics, Sphere, Surface, Geometric Transformations, Vectors
Applet is used to study the distribution of geometric medians on a sphere of radius R, „induces“ by the discrete sample of movable points in the 3-D space. On a circle- in Applet.
There is a set lP={P1, P2,...,Pn} of points and {(xi,yi,zi)∈ℝ3:i = 1,...,n} -their coordinates. Let a point (x,y,z) minimize a function of the sum of distances from this point to points lP. It is called Fermat's point https://en.wikipedia.org/wiki/Fermat_point or the Geometric median https://en.wikipedia.org/wiki/Geometric_median of the set lP.
Problem: find the positions of critical points (global minima and maxima too) of the function of sum of distances not only in the entire in the 3-D space, but on its bounded area.
Definitions of geometric medians can be generalized, in the sense that the critical points of the sum of distances function searched on a bounded area of 3-D space.
Geometric Medians on a bounded area (on a sphere), „induced“ by the points from 3-D space
The Geometric Median is defined here as point on a sphere from where the function of sum of the distances to each point Pi's have at that point: local minimums, maximums or saddle points.
Critical points can be found using Lagrange multipliers as (Λ(x,y,z,λ)=f(x,y,z)+λ*g(x,y,z)) finding the Extreme values of the function : f(x,y,z)= -sum of the distances from (x,y,z) to each point pi's, subject to a constraining equation: g(x,y,z)= . Let S be a sphere of radius R around the point O: S:={∈ℝ3: ||||=R}. I.e. it is necessary to find the critical points f(x,y,z) subject to: g(x,y,z)=0. Further we will use positional vectors :=(x,y,z)T : f(x,y,z)=and g(x,y,z):=-R=0. The gradients are: ∇f=and ∇g =/R -gradient of the magnitude of a position vector r. There is a system of equations: ∇f(x,y,z)= λ*∇g(x,y,z). A local optimum occurs when ∇f(x,y,z) and ∇g(x,y,z) are parallel, and so ∇f is some multiple of ∇g. The condition that ∇f is parallel to ∇g means ∇f = λ∇g.
☛ Thus, condition for a point c on a restricted region S to be GM is:
the resultant of all unit vectors from the set of points lP to this point ( ) is parallel to its positional vector , i.e. the angle Δφ between these two vectors is 0 or π (Fig. 2c and Fig. 2b in column Δα≟ π ).
There are no explicit Geometric Medians formulas, in contrast to Geometric Centers explicit formulas. The solution of the system of equations can be found use iterative procedures. I propose iterative procedures in which each step produces is a more accurate approximation:
=R*UnitVector() finds the Maxima - points and =R*UnitVector() finds the Minima - points. Iterative procedure to find Saddle points has a two-step combination:
=R*UnitVector(+m/R*); =R*UnitVector(), where m is the parameter that sometimes need to be configured in manual settings mode (Fig.1a and Fig.1b). These iterative formulas has the advantages of fast convergence speed for all initial positions.
You can visually observe (Fig. 1c) and explore single solutions max-Z1/min-Z2/saddle-Z3 in the manual settings mode (Fig. 1b) at points from the lP. Their coordinates (xi,yi) are set by moving the (x,y)Pi points and the coordinates zi -by moving the zi-points (Fig. 1a).
In the automatic settings mode click on Buttons: max min sad (in 4. Automatic search for critical points -Fig. 1c) and will get all the critical points.
![[size=85]Fig.1 Settings and control panels, observation windows.
a) -Settings and d) -relative position of the the "influence" points Pi around the sphere.
b) -Manual settings for finding critical points f(φ, θ) and determining the coefficient m for the saddle point search algorithm.
c) -(φ;θ) -plane of the angular coordinates of points on the sphere: Z1, Z2, Z3 -moving points (from b) of iterative solution search; f'[sub]φ[/sub]=0; f'[sub]θ[/sub]=0 -implicit functions of equations , their intersection are solutions of the Lagrange equations.
e) -graph of the distance sum function f(φ, θ).[/size]](https://www.geogebra.org/resource/cgtrjkpd/iJP0asrWG4lPFWDN/material-cgtrjkpd.png)
f(x,y,z): In the spherical coordinate system we will have a two-variable function f(φ,θ) over a rectangular region: - π ≤φ≤ π and π/2≤θ≤π/2. The two-dimensional surface plot of f(φ,θ) -function of sum of the distances for a point with angular position (φ,θ) on a sphere of radius R for a given location of points from the set lP is shown in Fig. 1e and Fig 2e.
The solution (critical points of a function f(x,y,z)) of the system of equations can be found too as the intersection points of the corresponding implicit functions and is shown in Fig. 1c and Fig. 2a.
By changing the positions of the points from lP (fig. 1a) you can find the positions of the geometric medians in ℝ3 on the bounded surface S. Distribution of points from lP in 3D and corresponding critical points max/min/sad (from Table -Fig. 2b) and directions for them "resulting all unit vectors" and position vectors on the surface of a sphere is shown in Fig. 2c. For illustration purposes, the vectors are attached to the points.
![[size=85]Fig.2 Results of explorations.
a) -Isolines and intersecting the implicit function equations of zeroing partial derivatives.
b) - Automatic search for critical points; their values.
c) -Distribution of points Pi, test Point, Max/min/saddle -Critical points on a sphere. Vectors ∇f and ∇g at these points.
d) -settings and e) -graph of the Two-variable function f(φ,θ) over a rectangular region: - π ≤φ ≤ π; -π/2≤θ≤π/2.[/size]](https://www.geogebra.org/resource/jqeqcxug/iFA0SdEkZl0JOXam/material-jqeqcxug.png)