# Online Uniformly Inserting Points on the Sphere +
## 2 Materials and Methods
### The Insertion Strategy  
A simple intuitive idea is to greedily insert the incoming point at the \"center\" of the largest empty spherical surface area. The early steps of such a greedy approach are simple; however, when many points have been inserted, the shapes of different local structures may vary significantly and the configuration may become very complicated. As a result, the computational cost of finding the largestempty spherical surface area and then computing its center may become prohibitive. Observe that once some points have been inserted, the sphere is partitioned into local structures and the next point insertion within the area of some local structure will only affect the local configuration there, i.e., the spherical distances (including the max gap and min gap) outside this area do not change. Based on this observation, a two-phase strategy can be devised. Let us consider a regular dodecahedron instead of the sphere. A regular dodecahedron has 12 identical regular pentagonal faces and 20 vertices, as shown in Figure 1a. For the convenience of computation, we can assume that the radius of the sphere is \(\sqrt{3}\) and thus the length of each edge of the corresponding regular dodecahedron is \(4/(\sqrt{5}+1)\). In the first phase, handling the insertion of 20 points on the sphere is quite straightforward: First insert eight orange points at vertices with coordinates \((\pm 1,\pm 1,\pm 1)\). Two arbitrary opposite vertices, for example, \(A\), \(C_{1}\), of the orange cube are inserted first, followed by the remaining 6 points in any arbitrary order. Then insert the remaining 12 points in any arbitrary order, as 6 structures of the same shape for every 2 points on the plane of the cube. The maximal gap ratio in this phase is proved to be 2.618 [13]. In the second phase, since the projection of the regular dodecahedron's edges divides the sphere into 12 identical curved surface areas, as shown in Figure 1b, we can consider point insertion in each local structure. In the previous work [13], we proved that for any two points \((P,Q)\) inside a pentagon (for example, as shown in Figure 2, \((P,Q)\in PentagonA\))\(BFE\), with \((P^{\prime},Q^{\prime})\) denoting their projection on the sphere), the gap ratio on the plane (pentagon) is smaller than that on the sphere, and we proved the difference can be reduced to 1.34 [13]. Therefore, the comparison between two spherical distances can be reduced to the comparison between two direct distances and the ratio would not change much. Figure 1: (**a**) The vertex distribution of the dodecahedron, with 8 orange vertices at \((\pm 1,\pm 1,\pm 1)\), and 12 blue vertices at \((0,\pm\phi,\pm\frac{1}{\phi})\), \((\pm\frac{1}{\phi},0,\pm\phi)\), and \((\pm\phi,\pm\frac{1}{\phi},0)\) (\(O\) is the center of the sphere and \(\phi=\frac{4}{\sqrt{5}+1}\approx 1.618\). ); (**b**) the projection of all the dodecahedron’s edges divides the sphere into 12 identical sections. Figure 2: The difference between segment in the plane and its projection on the sphere. We also proposed an insertion strategy in a pentagon in the previous work [13] as shown in Figure 3a, each pentagon can be partitioned into 1 smaller pentagon and 5 acute isosceles triangles with vertex angle of \(\frac{\pi}{5}\). An acute isosceles triangle can be further partitioned into 1 smaller acute isosceles triangle with vertex angle of \(\frac{\pi}{5}\), as shown in Figure 3b and 1 obtuse isosceles triangle with vertex angle of \(\frac{3\pi}{5}\), as shown in Figure 3c. An obtuse isosceles triangle can be partitioned into 1 acute isosceles triangle and 2 obtuse isosceles triangles. In this way, the pentagon is recursively partitioned into 3 types of shapes, which will be stored in 3 queues respectively. When a new point comes in, we first compare the insertions on the heads of these three queues and select the one with the largest minimal gap \(r\) if the point is inserted at an appropriate position.