I want to find a distribution of $n \in \mathbb{N}$ points on an ellipsoid $E$ such that the smallest distance between two points is as large as possible. Where for the distance between two points, we use their geodesics: $$g:E\times E \rightarrow \mathbb{R}^+$$

When I write "distance", I mean distance in the sense of g.

In the case $E = S^2$, i. e. the unit sphere, and $n = 32$ the voronoi-diagram of the points we are looking for would (propably) resemble a truncated icosahedron

I thought about a crude algorithm to apprximate a solution: each point can be parametrized by two angles. If we tweak those parameters of each point in a way, that we can increase distance to another point, one could repeat that (and more, see further) in a loop until some criteria is met.

Let $p,q \in E$. Since we can identify $p$ and $q$ by their angles, we can define $par(\theta_p,\phi_p) = p$ where we use the spherical coordinates of $p$. Now we want to see, how the distance between two points changes, if we tweak the spherical paramters of one of the points:

$$\delta_{p,q} :\mathbb{R}^2: \rightarrow \mathbb{R} \\ (\alpha, \beta) \mapsto \delta_{p,q}(\alpha, \beta) = g(par(\theta_p + \alpha, \phi_p + \beta), q)$$

Now, if we take the gradient $\nabla\delta_{p,q}(0,0)$ we could just climb along it to increase distance between the two points. For our purposes, we could find a weighted sum of gradients to update each point in relation to their $n-1$ remaining points. Let $P_n^0 = \{p_1^0,...,p_n^0\} \subset E$ be the set of $n$ points initially chosen.

for each p in $P_n^i$ $$u_{p} :=\sum_{q \in P_n^i} \nabla \delta_{p,q}(0,0) \omega(g(p,q))$$

with $\omega$ as a weight function, such that smaller distances get more weight in the sum than large ones.

We now set $P_n^{i+1} = \{par(par^{-1}(p_1^i) + u_{p_1^i}),...,par(par^{-1}(p_n^i) + u_{p_n^i})\} \subset E$

That is basically it.

further reading and ideas: https://stackoverflow.com/questions/9600801/evenly-distributing-n-points-on-a-sphere/9606368#9606368

  • $\begingroup$ What exactly is your question? $\endgroup$ – MvG Mar 22 '18 at 22:17
  • $\begingroup$ I'd like to know, if there is a problem with the idea. $\endgroup$ – dba Mar 23 '18 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.