July 22, 2019 at 08:56

Uniform distribution of points on a sphere

Original author: Martin Roberts
  • Transfer
The most uniform distribution of points on the sphere is an incredibly important task in mathematics, science, and computer systems, and applying a Fibonacci grid to the surface of the sphere using the same projection is an extremely fast and efficient approximation method for solving it. I will show how, with minor changes, it can be made even better.


Some time ago this post appeared on the Hacker News homepage. Its discussion can be read here .

Introduction


The problem of uniform distribution of points on a sphere has a very long history. This is one of the most well-studied problems in the mathematical literature on spherical geometry. It is of critical importance in many areas of mathematics, physics, chemistry, including computational methods, approximation theory, coding theory, crystallography, electrostatics, computer graphics, virus morphology and many others.

Unfortunately, with the exception of a few special cases (namely, Platonic solids), it is impossible to perfectly distribute points on a sphere. In addition, the solution of the problem strongly depends on the criterion that is used to assess uniformity. In practice, many criteria are used , including:

  • Packaging and coating
  • Convex hulls, Voronoi cells and Delaunay triangles
  • Kernels $ s $Rice Energy
  • Cubature and qualifiers

It is very important to clarify this aspect: usually there is no single optimal solution to this problem, because an optimal solution based on one criterion is often not an optimal distribution of points for others. For example, we will also find out that packaging optimization does not necessarily create an optimal convex hull and vice versa.

For the sake of brevity, in this post we will consider only two criteria: the minimum packing distance and the convex hull / Delaunay mesh (volume and area).

In section 1, we show how you can change the canonical Fibonacci grid to build an improved distribution of packaging . In Section 2, we show how you can change the canonical Fibonacci grid to build improved parameters for convex hulls. (volume and surface area).

Section 1. Optimization of packaging distance


Often this problem is called the Tamm's task in honor of the botanist Tems, who sought an explanation of the surface structure of pollen grains. The packing criterion requires us to maximize the smallest distance between neighbors for$ N $points. I.e

$ d_N = \ min_ {i \ neq j} | x_i - x_j | $


This value decreases with speed. $ ~ 1 / \ sqrt {N} $, therefore, it will be useful to determine the normalized distance, as well as the asymptotic limit of the normalized distance, as

$ d ^ * _ N = \ sqrt {N} d_N, \ quad \ quad d ^ * = \ lim_ {N \ rightarrow \ infty} d ^ * _ N $


Fibonacci grid

One very elegant solution models the nodes found in nature, for example, the distribution of seeds in a sunflower or pine cone. This phenomenon is called spiral phyllotaxis . Coxeter showed that such structures have a fundamental connection with the Fibonacci series,$ F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \} $ and the golden ratio $ \ phi = (1+ \ sqrt {5}) / 2 $.

In the literature, two similar definitions of the set of points of a spherical Fibonacci grid are found. The source is defined strictly for$ N $equal to one of the members of the Fibonacci series, $ F_m $, and well studied in number theory.

$ t_i = \ left (\ frac {i} {F_m}, \ frac {i F_ {m-1}} {F_m} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 $


The second definition generalizes the formula to an arbitrary amount $ N $ and is used in calculations more often:

$ t_i = \ left (\ frac {i} {N}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N \ tag {1} $


Where

$ \ phi = \ frac {1+ \ sqrt {5}} {2} = \ lim_ {n \ rightarrow \ infty} \ left (\ frac {F_ {n + 1}} {F_n} \ right) $


Below is an example of the same Fibonacci grids. By transformation, you can turn these sets of points into Fibonacci spirals that are well known to us.

$ (r, \ theta) = (\ sqrt {x_1}, 2 \ pi x_2) $



Similarly, these sets of points can be transferred from the unit square $ [0, 1] ^ 2 $ on a sphere using a cylindrical isometric projection:

$ (x, y) \ rightarrow (\ theta, \ phi): \ quad \ left (\ cos ^ {- 1} (2x-1) - \ pi / 2, 2 \ pi y \ right) $


$ (\ theta, \ phi) \ rightarrow (x, y, z): \ quad \ left (\ cos \ theta \ cos \ phi, \ cos \ theta \ sin \ phi, \ sin \ theta \ right) $


Many different versions of Python code for it can be found on stackoverflow: Evenly distributing points on a sphere .

Even despite the fact that spherical Fibonacci sets are globally not the best distribution of samples on a sphere (because their solutions do not coincide with the solutions for Platonic solids for$ n = $ 4,6,8,12,20), they have excellent sampling properties and are very easy to build compared to other, more complex spherical sampling schemes.

Since the transfer from the unit square to the surface of the sphere is carried out by a projection with conservation of area, it can be expected that if the starting points are distributed evenly, they will also be fairly well distributed on the surface of the sphere. However, this does not mean that the distribution will be provably optimal.

This transfer suffers from two different but interrelated problems.

Firstly, this overlay is performed while maintaining the area, not the distance. Given that in our case, the condition is to maximize the minimum pairwise distance between points, such conditions and relationships will not necessarily be satisfied after projection.

The second problem is most difficult to solve from a practical point of view: the superposition has two degenerate points at each pole. Consider two points that are very close to the pole, but differing by 180 degrees in longitude. On a single square (and on a cylindrical projection) they will correspond to two points very distant from each other, but when superimposed on the surface of a sphere they can be connected by a very small arc passing through the north pole. Because of this particular problem, many spiral overlays are not optimal enough.

The Fibonacci Spherical Helix obtained from Equation 1 gives the value $ d_N ^ * $ for all $ N $, i.e $ d ^ * = 2 $.

Grid 1

A more common version (especially on computer systems) that creates a better value$ d ^ * = 3.09 $has the form:

$ t_i = \ left (\ frac {i + 1/2} {N}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {2} $


It places the points at the midpoints of the intervals (according to the midpoint rule in the Gauss quadratic formula), therefore, for $ n = 100 $, the values ​​of the first coordinate will be as follows:

$ \ {\ frac {0.5} {100}, \ frac {1.5} {100}, \ frac {2.5} {100}, \ ldots, \ frac {97.5} {100}, \ frac {98.5} {100} , \ frac {99.5} {100} \} $


Grid 2.

The key to further improving Equation 2 is the realization that$ d ^ * _ N $ always corresponds to the distance between points $ t_0 $ and $ t_3 $that are at the poles. That is, to improve$ d_N $points near the poles should be spaced even further.

If we define the following distribution:

$ t_i (\ varepsilon) = \ left (\ frac {i + 1/2 + \ varepsilon} {N + 2 \ varepsilon}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \ ; 0 \ leq i \ leq N-1 $


$ d ^ * _ N $ - curves for various values. $ \ varepsilon = 0 $ (blue); $ \ varepsilon = \ frac {1} {2} $ (orange); $ \ varepsilon = \ frac {3} {2} $(green); and$ \ varepsilon = \ frac {5} {2} $(red). You can see that$ \ varepsilon = \ frac {5} {2} $gives results closer to asymptotic results. That is, with$ N> 20 $ The following simple expression generates significantly better results. $ d ^ * = 3.29 $ compared to the canonical spherical Fibonacci grid:

$ t_i = \ left (\ frac {i + 3} {N + 5}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {3} $


That is, with $ N = 100 $ the values ​​of the first coordinate will be equal to:

$ \ {\ frac {3} {105}, \ frac {4} {105}, \ frac {5} {105}, \ ldots, \ frac {100} {105}, \ frac {101} {105} , \ frac {102} {105} \} $



Figure 1. Different values $ d_N ^ * $ at different values $ \ epsilon $. The higher the value, the more optimal the configuration. We see that$ \ epsilon \ simeq 2.5 $provides a solution close to optimal.

Grid 3.

As mentioned above, one of the most serious problems of uniform distribution of points on a sphere is that the distribution optimality critically depends on the objective function used. It turns out. that local quantities like$ d_N ^ * $sometimes they almost “do not forgive mistakes” - a single point in an insufficiently optimal position can catastrophically reduce the assessment of the entire distribution of points.

In our case, regardless of the magnitude$ N $ value $ D_N ^ * $ usually defined by the four points closest to each of the poles, especially $ t_0 $ and $ t_3 $. However, it is also known about this grid that the largest Voronoi polygon is at the pole. So trying to maximize$ d_N $by dividing the original polar points in a row, we actually increase the void at the pole even more! Therefore, we presented an alternative to grid 2, which is generally preferable because it does not show such a large void near the poles.

It is almost identical to grid 2, but has two differences. First, she uses$ \ varepsilon = 11/2 $ at $ 1 \ leq i \ leq N-2 $. Secondly, besides these$ N-2 $The first and last points are located at each of the poles.

I.e:

$ t_0 = (0,0); \; t_n = (1,0); \ quad t_i = \ left (\ frac {i + 6} {N + 11}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 1 \ leq i \ leq N-2 \ tag {4} $


An amazing property of this construction method is that despite the fact that its creation was motivated by a desire to minimize voids at the poles, it actually has the best value among all methods $ d_N $ and $ d ^ * $ from $ d ^ * = 3.31 $!

That is, with$ N = 100 $ the values ​​of the first coordinate will be as follows:

$\{ 0; \; \frac{7}{111},\frac{8}{111},\frac{9}{1111},\ldots, \frac{102}{111},\frac{103}{111},\frac{104}{111} ; \; 1\}$



Figure 2. Various grid configurations. The canonical Fibonacci grid on the left. Note that even though the middle grid$d_N^*$improved, at the pole she has a noticeable void. Grid 3 has no void at the pole and has the best value$d_N^*$.

Comparison

At large values$N$ this value $d^*$extremely well comparable with other methods, for example, geodesic domes, which are based on triangulated projections from the faces of Platonic solids onto the surface of a sphere. It is not surprising that the highest quality geodesic domes are built on the basis of the icosahedron or dodecahedron.

Icosahedron-based geodesic domes at various values$N$.

$\begin{array}{|c|cccccccccc|} \hline N & 12 & 42 & 92 & 162 & 252& 362 & 492 & 642 & 812 & 1002 \\ \hline d^* & 3.64 & 3.54 & 3.34 & 3.22 & 3.15 & 3.09 & 3.06 & 3.03 & 3.00 & 2.99 \\ \hline \end{array}$


Dodecahedron-based geodesic domes for various values $N$.

$\begin{array}{|c|ccccccc|} \hline N & 20 & 32 & 122 & 272 & 482 & 752 & 1082\\ \hline d^* & 3.19 & 3.63 & 3.16 & 2.99 & 2.90 & 2.84 & 2.81 \\ \hline \end{array}$


In addition, a truncated icosahedron corresponding to the shape of fullerene $C_{60}$has only $d^* = 3.125$.

That is, with$N>100$mesh based on equation 3 is better than any geodesic polyhedron.

According to the data from the first source in the list of references below, some of the modern methods, which are usually complex and require recursive and / or dynamic programming, have the following indicators.

$\begin{array}{|lr|} \hline \text{Lattice 1} & 3.09\\ \hline \text{Max Determinant} & 3.19 \\ \hline \text{Lattice 2} & 3.28 \\ \hline \text{Lattice 3} & 3.31 \\ \hline \text{Zonal Equal Area} & 3.32 \\ \hline \text{Coulomb} & 3.37 \\ \hline \text{Log Energy} & 3.37\\ \hline \end{array}$


Conclusion from Section 1

Grid 3, created by Equation 3, is a modification of the canonical Fibonacci grid, which provides much better packaging for the distribution of points. I.e

$t_0 = (0,0); \; \; t_i = \left( \frac{i+6}{N+11}, \frac{i}{\phi} \right); \;\; t_{N-1} = (0,1); \quad \textrm{for }\; 1 \leq i \leq N-2$


Section 2. Optimization of the convex hull (Delaunay mesh)


In the previous section, we optimized the distribution by $d^*_N$However, these modifications worsen other indicators, for example, the volume of a convex hull (Delaunay mesh). This section describes how to evenly distribute points on a sphere in such a way as to optimize (maximize) such a more global indicator as the volume of a convex hull.

We denote$C_N$ like a convex hull $N$ points

$\epsilon_N = N \left( \frac{4\pi }{3} \; – \textrm{Vol}(C_N) \right)$


normalization factor included $N$, because the absolute discrepancy decreases with speed $~ 1/N$.

Behavior$\epsilon_N$ at various $N$can be seen in Figure 3 (blue line).

To reduce the mismatch of volumes, it should be noted that despite the use of$\phi$, from the logic of the golden section at $N \rightarrow \infty$ it does not necessarily follow that it is the best value for the final $N$. Speaking scientifically, we can say that we need to take into account the influence of limb limb correction.

Let's summarize equation 1 as follows:

$t_i = \left( \frac{i+1/2}{N}, \frac{i}{g(N)} \right) \quad \textrm{for }\; 0 \leq i \leq N-1 \tag{4}$


where we define $g(n)$ as

$g(n) = \begin{cases} 3-\phi, & \text{if $k$ is even} \\ \phi, & \text{if $k$ is odd} \end{cases} \tag{5}$


Where

$k = \left\lfloor \textrm{log}_{\phi}(\frac{n}{1.5}) \right\rfloor = \left\lfloor \frac{\ln (n/1.5)}{\ln \phi } \right\rfloor$


Where $\lfloor x \rfloor$- the function of rounding to the nearest integer down.

Figure 3 shows how much volume mismatch is optimized for half of the values.$N$.

The reason for this is a little-known fact: all numbers$x$satisfying the special Mobius transformation, starting from irrationality, are equivalent $\phi$.

$x = \frac{a\phi+b}{c\phi+d}, \quad \textrm{for all integers} \; \; a,b,c,d \; \textrm{such that } |ad-bc|=1$


Therefore, the reason that $\phi$ and $3-\phi$ fit together so well, is that

$\frac{1}{\phi} = \frac{\phi+1}{2\phi+1}, \quad \quad \frac{1}{3-\phi }= \frac{2\phi+1}{1\phi+1}$



Figure 3. The mismatch between the volume of the convex hull of points and the volume of the unit sphere. Keep in mind that the smaller it is, the better. The figure shows that the hybrid model (orange line) based on$\phi$ and $3-\phi$, provides a better distribution of points than the canonical Fibonacci grid (blue line).

For the remaining half, we first define an auxiliary series$A_N$being a variation of the Fibonacci series

$A_1 =1, \; A_2 = 4; \; A_{n+2}= A_{n+1}+A_n \; \textrm{for } n = 1,2,3,…$


I.e

$A_N = 1,4,5,9,14,23,37,60,97,157,254,411,…$


All fractions of this series have elegant continuous fractions, and in the limit converge to $\phi$. For instance,

$t _5/t_4 = 1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{4}}}}$


Now we can fully generalize $g(n)$ in the following way:

$g(N) = \begin{cases} 3-\phi, & \text{if $k$ is even} \\ A_{j+1}/A_j , & \text{if $k$ is odd, where $j= (k+7)/2$} \end{cases} \tag{6}$


The table below shows the values $g(N)$ for various $N$.

$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline N & 4-6 & 7-10 & 11-16& 17-26& 27-43& 44-70& 71-114 & 115-184 & 185-300\\ \hline g(n) &3-\phi & \frac{23}{14} & 3-\phi & \frac{37}{23} & 3-\phi & \frac{60}{37} & 3-\phi & \frac{97}{60} & 3-\phi \\ \hline \end{array}$


Figure 4 shows that with respect to the volume of the convex hull, this new distribution is better than the canonical grid for all values $n$


Figure 4. The mismatch between the volume of the convex hull and the volume of the unit sphere. The lower the value, the better. This tells us that the proposed new method (green line) constantly provides a better distribution than the canonical Fibonacci grid (blue line).


Figure 5. Visual comparison of the canonical mesh (left) with the new modified mesh (right) with n = 35 and n = 150. Visually, the differences are almost imperceptible. However, in conditions requiring maximum efficiency, the modified version (on the right) provides a small, but quantifiable improvement in both volume and surface area of ​​the convex hull.

Curiously, this distribution is also insignificant, but steadily reduces the mismatch between the surface area of ​​the convex hull and the surface area of ​​a single sphere. This is shown in Figure 6.


Рисунок 5. Нормализованное рассогласование площадей между площадью поверхности выпуклой оболочки (сетки Делоне) и площадью поверхности единичной сферы. Чем ниже значения, тем лучше. Это показывает, что предложенная новая модификация (зелёные точки) демонстрирует небольшое, но постоянное снижение разности площадей поверхностей по сравнению с канонической сеткой Фибоначчи (синие точки)

Вывод из раздела 2

Сетка, соответствующая уравнению 6, является модификацией канонической сетки Фибоначчи, создающей значительно лучшее распределение точек, исходя из объёма и площади поверхности выпуклой оболочки (сетки Делоне).

Источники

Tags:

Also popular now: