Method of Lagrange multipliers. Placing points on a circle/sphere such that the each point is the geometric median of all its other points.
- Author:
- Roman Chijner
Main Problem: to find the algorithm of finding a uniform distribution of points on a sphere.
Search method: to find critical points of "specific" functional dependencies and understand "by simple models " to which particle distributions this leads.
The main idea of this applet - to find on the circle/sphere such location of points, that each of them is at the point of the geometric median of its other points, i.e. to maximize the sum of the mutual distances of all particles:
Applet. Method of Lagrange multipliers. Relative positioning of "repulsive" movable points on a circle
Applet. Finding the optimal relative position of the" repulsive " set of particles on the circle
Applet. Finding the optimal relative position of the" repulsive " set of particles on the sphere
Applet Some cases of polyhedra with an extreme distribution of their vertices on the surface of a sphere.
Applet. Polyhedra whose vertices are equivalent and have an extreme distribution on the same sphere.
Applet. Example of non-uniqueness of the extreme distribution of n=16 particles on the surface of a sphere.
Applet. 3d shapes: n=72. Extreme distribution of points on the surface of a sphere and comparison with two known but not extreme ones having the same number of vertices
Images. Placing points on a sphere such that the each point is the geometric median of all its other points.
The Geometric Median(GM) of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points or Fermat point Fo. Let us generalize this definition for a set of "repulsive" points on the surface of a circle/sphere. Obviously, here is relevant the point on a circle/sphere, maximizing the sum of distance (Distance Sum) between every possible pair of points on a circle/sphere. It is of interest to find out such mutual arrangement of repulsive set of particles on a sphere, when each point of this set is Geometric Median(GM) of the remaining n-1 points. We assume that the equilibrium - stationary state in system of charges is reached if the sum of their mutual distances is maximal. Iterative approach of particle placement is applied for achieving a stationary state.
Problem statement: to place n points on the circle/sphere so that each point is located at a position of geometric median of remaining n-1 others points. And it is necessary to take into account the restriction: each this point must remain on the original circle/sphere.
The problem is solved by the method of Lagrange multipliers to maximize the the function of sum of distances (Distance Sum). The proposed iterative procedure is applied sequentially to each point until the correction vectors will not be parallel to their corresponding positional vectors: the gradient of the Distance Sum is perpendicular to the constraint-circle/sphere.
In the following, we will consider the case of distribution of points on the sphere.
Spherical Distribution of n Points with Maximal Distance Sum
Solution method: There is a set lP={p1, p2,...,pn} of points on a sphere and {(xi,yi,zi)∈S:i= 1,...,n} -their coordinates. Let S be a sphere of radius R centered at the origin (O): S:={||||∈ℝ³: ||||=R}.
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 multipliersas (Λ(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)= - point (x,y,z)∈S. 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. 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.
![[size=85][i][color=#333333]There are no [i]explicit[/i] [color=#ff7700]Geometric Medians[/color] formulas, in contrast to [color=#ff00ff]Geometric Centers[/color] explicit formulas.
[/color][/i][i][color=#333333][i][i][i][color=#333333][b]In our case[/b], [/color][/i][/i][/i]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. [color=#333333][i] Relationship between vectors of two consecutive iterations[i][i][color=#000000][i] is defined by[/i][/color][/i][/i][/i][/color][/color][/i] [math]\vec{r_s}^{^{\text{✱}}}=[/math][math]\text{R*UnitVector(}\sum_{i=1}^{n,i\text{≠}s}UnitVector\left(\vec{r}_s-\vec{r_i}\right)\text{)}[/math][color=#222222][color=#1e84cc][i][color=#333333] finds the [/color][color=#ff0000]Maxima -[/color][color=#333333] points. [i][i] That means that the [/i][/i][/color][/i][/color][/color][math]\vec{f_s}[/math][color=#222222][color=#1e84cc][i][color=#333333]:= [/color][/i][/color][/color][math]\sum_{i=1}^{n,i\text{≠}s}UnitVector\left(\vec{r}_s-\vec{r_i}\right)[/math][color=#222222][color=#1e84cc][i][color=#333333][i][i] (sum of unit vectors [i][color=#333333][i][color=#000000][i][color=#333333]location of a point p[sub]s[/sub] relative to others n-1 points[/color][/i][/color][/i][/color][/i][/i][/i][/color][/i][/color][/color]) [color=#222222][color=#1e84cc][i][color=#333333] [i][color=#000000][i][color=#333333]-is the collective "force" action at point p[sub]s [/sub][/color][/i][/color][/i][/color][/i][/color][/color] (as shown on the Fig. 1 above[color=#222222][color=#1e84cc][i][color=#333333][i][color=#000000][i][color=#333333][sub][i] [/i][/sub][/color][/i][/color][/i][/color][/i][/color][/color][color=#222222][color=#1e84cc][i][color=#333333][sub][/sub]. [/color][/i][/color][/color][i][color=#222222][i][i]All points are successively corrected until the system of points comes to a stationary state. Finally, at the end of iterations they must match p[sub]s[/sub][/i][/i][sup]✱[/sup][/color][sub][/sub]=p[sub]s[/sub] for all s=1,2,...,n [/i][i][color=#000000][i][color=#333333]and vectors f[sub]s[/sub] will be perpendicular to the surface [b]S[/b] of the sphere at all points from lP. [/color][/i][/color][color=#000000][i][color=#333333]The iteration is terminated when t[/color][color=#333333]he center of mass of n particles on a sphere (with a certain degree of accuracy) will not be in the center of the sphere).[/color][/i][/color][/i][i][color=#000000][i][color=#333333]
[color=#1e84cc][i][color=#222222][i][i][i][color=#ff0000][b] Spherical Distribution of n Points with Maximal quadrat [i][color=#222222][i][i][i][color=#ff0000][b]Distance Sum[/b][/color][/i][/i][/i][/color][/i]
[/b][/color][/i][/i][/i] [i][b][b][u]Solution method[/u][/b][/b][/i][i]: [/i]The [/color][color=#ff00ff]Geometric Center [/color][color=#222222]is defined here as [/color][color=#333333][b]point [/b][/color]on sphere from where[color=#333333] the [/color][color=#1e84cc]sum of the [i]squares[/i] of all Euclidean distances[/color][color=#333333] [color=#222222][color=#222222][color=#222222][color=#222222][color=#222222]to each point p[sub]i[/sub]'s have at [/color][b]that point[/b][/color][/color][/color][/color][/color][/i][/color][/color][/i][/color][/i][i][i][i][i][i][color=#333333]: [/color][/i]local [color=#0000ff]minimum[/color], [color=#ff0000]maximum [/color][color=#93c47d][color=#222222]or [/color][color=#222222]a [/color][color=#6aa84f]saddle[/color] points.
[/color][color=#333333] Critical points can be found using [/color][b][color=#333333]Lagrange multipliers[/color][/b][/i][b][color=#333333]as [/color][/b]([i]Λ(x,y,z,λ)=f(x,y,z)+[color=#ff7700]λ[/color]*g(x,y,z))[/i] finding the Extreme values of the function :
[i] f[sub]q[/sub](x,y,z)=[math]\sum_{i=1}^n\left[\left(x-x_i\right)^2+\left(y-y_i\right)^2+\left(z-z_i\right)^2\right][/math][/i] -[/i][color=#1e84cc]sum of the squares of the distances[/color] to the points pi[/i][/i][color=#333333], [/color]subject to a constraining equation:
[color=#333333]g(x,y,z)=x[/color][sup]2[/sup][color=#333333]+y[/color][sup]2+[/sup]z[i][sup]2[/sup][color=#333333]-R[/color][sup]2[/sup][color=#333333] -[i] points (x,y,z)∈[b]S.[/b][/i][/color] [i][i][color=#333333] I.e. it is necessary to find the critical points f[sub]q[/sub](x,y,z) subject to: g(x,y,z)=0. [/color][/i][/i][color=#6a6a6a]Let's denote the resulting point as Sum(lP):[color=#333333]=[math]\sum_{i=1}^np_i[/math] , then [/color][/color]∇f/2=n*(x,y,z)-[/i][math]\left(\sum_{i=1}^nx_i,\sum_{i=1}^ny_i,\sum_{i=1}^nz_i\right)[/math][i][i][i] or ∇f/2=n*(x,y,z)-Sum(lP)[/i][color=#333333] and [/color][color=#333333]∇g/2=(x,y,z): ⇒[/color][b](x,y,z)∼Sum(lP)[/b][color=#333333].
The point (x,y,z) [/color][i]that minimize the [color=#1e84cc]sum of the squares of the distances[/color] to the points [/i][color=#333333]p[/color][color=#333333][sub]i[/sub] [/color][i][color=#333333]is the [/color][i][b][color=#ff00ff]Geometric Center[/color][/b] ([i][color=#333333]gravity center, [/color][/i][i]barycenter, [/i][url=https://en.wikipedia.org/wiki/Center_of_mass][i]center[/i][i] [/i][i]of mass[/i][/url][i], [/i][i]centroid)[/i] [/i][color=#ff00ff]GC[/color][color=#333333]: [/color][color=#ff00ff][b]Cm[/b][/color][color=#333333]=[/color][math]\frac{\sum_{i=1}^np_i}{n}[/math][/i][i][color=#333333][b] -[/b]its coordinates are the averages of the coordinates of the points from set lP[/color].
[/i][/i][/i][color=#333333] [b]In our case[/b], the position of the points on a sphere must be defined as: [math]\vec{r_s}[/math][i][color=#333333][sup]✱[/sup]=R*[i][size=100]UnitVector[/size][/i]([/color][/i] [math]\frac{\sum^{n,i\ne s}_{i=1}\left(\vec{r_i}\right)}{n-1}[/math]) and [math]\vec{f_s}[/math]:=[math]\frac{\sum^{n,i\ne s}_{i=1}\left(\vec{r_i}\right)}{n-1}[/math]. [/color][color=#000000][i]However, this iteration scheme does not converge. Iterations in this case do not lead to stationary positions of the particles.
[/i][size=85][b]Notation in applets:
[/b] [math]\vec{r}[/math][sub]position vector[/sub][i](s)∼lP(s) -position vector for each point s;
[/i][math]\vec{f}[/math][color=#ff0000][sub]GM vector[/sub](s) [/color][color=#ff0000]∼Sum[Zip(UnitVector(lP(s)-a),a,lP\lP(s))] - [/color][color=#333333]the vector [math]\vec{f_s}[/math] of the geometric median([/color][color=#ff7700]GM[/color][color=#333333]) at point p[sub]s[/sub] caused by the „action“ of the remaining (n-1) points;
[/color] [math]\vec{f}[/math][sub][color=#ff00ff]GC vector[/color][/sub][color=#ff00ff](s) ∼Sum[lP\lP(i)]/(n-1) - [color=#333333]the vector [math]\vec{f_s}[/math] of the geometric center([/color]GC[color=#333333]) at point p[sub]s[/sub] caused by the „action“ of the remaining (n-1) points;[/color]
[/color][color=#ff0000] Δφ[sub]s:[/sub][/color][color=#ff00ff]=[/color][color=#333333]Angle([/color][math]\vec{r}[/math][color=#333333][sub]position vector[/sub](s),[/color][math]\vec{f}[/math][color=#ff0000][sub]GM vector[/sub](s)[/color][color=#ff0000]);
[/color][color=#ff00ff] Δφ[sub]s:[/sub][/color][color=#ff0000]=[/color][color=#333333]Angle([/color][math]\vec{r}[/math][color=#333333][sub]position vector[/sub](i),[/color][math]\vec{f}[/math][color=#ff00ff][sub]GC vector[/sub](s)).[/color][/size][/color][/size]](https://www.geogebra.org/resource/yjvxjkb6/SImjBJTMlTZ12F50/material-yjvxjkb6.png)
![[color=#333333][i][size=85][b]Results. [/b] [i][i][i][color=#000000] In the applet in the tables, you can see the angular distances [i][i][i][color=#000000]Δφ[sub]i[/sub][/color][/i][/i][/i] between position vectors and corresponding vectors of geometric medians and centers for each particle. In the equilibrium state (as it is demonstrated by calculations), the positions of the points on the sphere are both geometric medians and geometric centers of other points on the sphere. Correction angles are Angle measurement between the corresponding Black and Orange Vectores. The condition Δφ[sub]i[/sub] → 0 is an equilibrium condition for “repulsive” points on the surface of the sphere: there are no “tangential forces” that will move them on the surface of the sphere. [i][size=85][i][i][i][color=#000000]The mean of the sum of all correction angles Geometric medians-[color=#ff7700]GM[/color] and Geometric centers-[color=#ff00ff]GC [/color]Δφ[sub]s[/sub] tend to zero too. [color=#333333]Denote these values respectively as [/color][color=#ff7700]Δφ[sub]GM[/sub][color=#333333] and [/color][/color][color=#ff00ff]Δφ[sub]GC[/sub][/color][color=#ff7700] .[/color][/color][/i][/i][/i][/size][/i]
For symmetric structures, the length of the position vectors of the Fermat point [color=#ff7700]F[sub]o[/sub] [/color][color=#333333]and[/color]centroid [color=#ff00ff]Cm [/color]tends to zero. Let us denote by [color=#ff00ff]ΔCm[/color] and [color=#ff7700]ΔF_o[/color] -the deviations of these values with respect to the center of the sphere. [/color][/i][/i][/i][/size][/i][/color]](https://www.geogebra.org/resource/pv8kp2ej/Tmi2oTHHVwlRZLvl/material-pv8kp2ej.png)
Explanation. In the case of points on a sphere: stop animation is performed by pressing the button-Stop or automatically, provided that the geometric center of the points coincides (with a certain degree of accuracy) with the center of the sphere: ΔCm<2*10-k.
In the upper left part of the applet there are in two columns two (for convenience of comparison) subsequent iterations of the Distance Sum. Their values are calculated as the average distance between particles on the Unit Sphere : Distance Sum/[0.5*n*(n-1)*R].
The table of values of these values for different values n are given in https://www.geogebra.org/m/qmguscwp.