Evenly Spaced Points On Smooth Surface

Question

I want to space points evenly (i.e. maximizing minimal distance between two points) on some smooth surface $S\subseteq\mathbf{R}^n$ (usually $n=3$), where I have a projection operator $p:\mathbf{R}^n\to S$ which approximates the closest point on the surface. My idea is to place them randomly first and then let some repelling force act between them and reproject back to the surface after each iteration of the action. This can be rather costly, if there are $10^3$ points, I have to compute the distance between $10^6$ points in one iterations, and I need a few iteration until everything stabilizes.

How can I imporove this process? My ideas:

• Measure the distance between every pair of points but compute the force only when the distance is smaller than some $a$, then do a few iterations (assuming the points don't move too far in one iteration) and recompute the distance after $k$ steps.
• Choose some partition of the surface where each part has a set of 'neighbours' (including itself), compute for each point the location in the partition, i.e. the part it lies in, then let only the points in neighbouring parts act on each other, recompute the location after $k$ steps.

Answer 1

I would suggest that you don't calculate the distance between all pairs of points, but only between pairs of points that are nearest neighbors. You could store the points in some nearest-neighbor data structure, e.g., an octree, or even a fixed partitioning of space. Some data structures might allow for relatively rapid updates, so you could even update after every iteration.

I'd also suggest looking at the methods used for simulating the n-body problem, as some of those might be applicable to your situation as well. See https://en.wikipedia.org/wiki/N-body_problem#Many_bodies and https://en.wikipedia.org/wiki/N-body_simulation.

Also, you might consider adapting your objective function. Rather than having all points repel, maybe you might have only those points whose neighbor are below a certain threshold repel; or you might make the repelling force a smooth function of the distance between the points, where this function is similar to $f(x) \approx x$ when $x \ll \tau$ (where $\tau$ is the threshold) and $f(x) \approx \tau$ when $x \gg \tau$. You could select your threshold $\tau$ to be approximately equal to the expected final minimal distance that you think is achievable, or you could set it adaptively in each iteration. This may require many more iterations, but each iteration can be done much faster, and it will avoid moving points that are already far from all their neighbors.