Distance between points inside a sphere

[OmegaGuy]

Let's say you have a sphere with volume x. Inside it are y amount of points, spaced equally (equidistant from each other). How would you determine the distance than an object (starting from the center of the sphere) would take to visit each point once?

Sorry if this is a stupid question with an obvious answer that I'm overlooking.

[Steel]

Well if you imagine the points all arrayed in a grid fashion, and then starting from the centre you head on any line of points that takes you to the edge of the sphere. From there go to the line that runs parallel to the one you just headed along, and continue along that until you get to the other side of the sphere, then drop to the line below that and continue in this pattern till you have been to all the points in a semi circle. Then jump up a column and repeat the process for the next plane of points until you have been through a quarter of the points in the sphere. Then move to the nearest unvisited quarter and continue till youve covered the whole sphere.

This might not be the most efficient method, but you can see that you never end up covering dignificantly more distance that the spacing distance between the points. If the number of points is large, you can basically say that the distance you need to travel is y*(spacing) (and if y is very small, you can measure it )

This is a (very) special case of the travelling salesman problem in 3d. Becuse of the very ordered nature of the points it is possible to find the answer in closed form if you give it a go. Might take a few minutes though.

Try putting a grid of points in a circle and then seeing the most efficient path to cover all of them. Could also be easier to reformat your problem in terms of a sphere of radius r (and therefore x=4/3 pi r^3 )

[Darth Holbytlan]

It's impossible to have more than 4 points equidistant from each other in three dimensions (unless they are all in the same spot). So this problem can only have interesting answers for y = 2, 3, 4. Plus, as written, the sphere isn't contributing to the problem. Perhaps you meant that the points are on the surface of the sphere? Even then, the problem doesn't have a fixed solution for 2 and 3 points.

Of course, if you know the points are separated by distance d, then the total length is d*(y-1) + r, where r is the distance from the center of the sphere to a point (the radius of the sphere if they are on the surface).

[Kuroneko]

Darth Holbytlan is correct about not being able to find more than four equidistant points; however, if the points are restricted to the surface of a sphere (thus injecting some sort of relevance for even mentioning it), there is an interesting related problem of having n equidistributed points. This trivially opens up the obvious cases of n = 6,8,12,20, corresponding to the vertices of the Platonic solids. For example, for n = 6 points on a unit sphere (circumscribing an imaginary octahedron), the geodesic distances between distinct points are all either π/2 or π units, so they're not equidistant, but they are in some sense equidistributed. For n points, we may be able to say they're equidistributed if their locations form an equilibrium for a system of equally charged particles on confined to a sphere, or some similar criterion, but this seems to be in general a very difficult problem.

[OmegaGuy]

I'm talking about points inside a sphere, not on the surface. I guess equidistant was the wrong word to use though, but it seems as if it's unsolvable, especially since I'm trying to solve it for a very large number of points.

[Surlethe]

I'm talking about points inside a sphere, not on the surface. I guess equidistant was the wrong word to use though, but it seems as if it's unsolvable, especially since I'm trying to solve it for a very large number of points.

Is it possible to clarify your question, then? Do you have the points lying on a sphere inside the big sphere? Is each point some constant distance from the nearest point, like on a lattice?

[OmegaGuy]

Is each point some constant distance from the nearest point, like on a lattice?

Yes, that's correct.

[Surlethe]

So would it be more accurate to rephrase your question as follows?

"Let a sphere of radius r be centered at the origin in R^3. Consider the elements of Z^3, as a subset of R^3, enclosed within the sphere. What is the minimum distance a pointer must travel, starting at the origin, to hit each of these lattice points once and only once?"

[Steel]

So would it be more accurate to rephrase your question as follows?

"Let a sphere of radius r be centered at the origin in R^3. Consider the elements of Z^3, as a subset of R^3, enclosed within the sphere. What is the minimum distance a pointer must travel, starting at the origin, to hit each of these lattice points once and only once?"

Well i think here 'and only once' is superfluous as we are looking for the minimum distance, which already eliminates any paths which unnecessarily double back.

[OmegaGuy]

Yes, how would you solve that?

[Gil Hamilton]

Isn't that a traveling salesman problem?

[Kuroneko]

Taking Surlethe's version of the problem, let N(n;r) = |{x∈ℤⁿ: |x|≤r}| be the number of integer-lattice points in n dimensions within a radius r of the origin. Then, letting F(·) be the floor function, it is obvious that
[1] N(n,r) = 1 for r<1, N(1,r) = 1+2F(r).
We can also slice any (n-1)-sphere into (n-2)-spheres, so the N(n;r) is composed of terms in the form N(n-1;sqrt(r²-k²)), which count the number of lattice points x = (x_0,x_1,...,x_{n-1}) with x_0 = k. Therefore, the recurrence relation for N(n;r) is
[2] N(n;r) = N(n-1,r) + 2Sum_{k=1}^{F(r)} N(n-1,sqrt(r²-k²)),
so that for n = 2,
[3] N(2;r) = 1 + 4F(r) + 4Sum_{k=1}^{F(r)} F(sqrt(r²-k²)),
Iterating it one more time yields a formula for the sphere. For n = 3 and integer r = k, the sequence is 1, 7, 33, 123, 257, 515, 925, 1419, 2109, 3071, ... (Sloane's A000605; A117609 for r = sqrt(k)). See also Gauss's Circle Problem.

Even the number of lattice points is rather nontrivial, e.g., N(3;9) = 3071 but N(3;9.06) = 3119, so I very much doubt that as stated your problem has a 'nice' solution. Perhaps an algorithmic solution would be better, although guaranteeing it to be minimal would be difficult. Out of curiosity, what exactly are you doing with this?

[Ariphaos]

Darth Holbytlan is correct about not being able to find more than four equidistant points; however, if the points are restricted to the surface of a sphere (thus injecting some sort of relevance for even mentioning it), there is an interesting related problem of having n equidistributed points. This trivially opens up the obvious cases of n = 6,8,12,20, corresponding to the vertices of the Platonic solids. For example, for n = 6 points on a unit sphere (circumscribing an imaginary octahedron), the geodesic distances between distinct points are all either π/2 or π units, so they're not equidistant, but they are in some sense equidistributed. For n points, we may be able to say they're equidistributed if their locations form an equilibrium for a system of equally charged particles on confined to a sphere, or some similar criterion, but this seems to be in general a very difficult problem.

There are (at least) three rather novel means of attempting to do this for very large values of n.

One way is to take n number of slices, with one slice being the north pole, and the other on the south pole, and attempt to get a close equidistribution by placing them in a spiral around the sphere. This is good if you don't want to put a map on it, but at the very least you can solve the OP's problem rather easily.

Another way, also described above, is to use subdivisions (also described in above link). You make an icosohedron (meaning you have twelve pentagons), and subdivide the triangles into lots and lots of hexagons. This works very nicely for a map, but doesn't preserve directions well.

A third method I began developing on my own before abandoning it to the above is to brute-force hexagons at latitudes around the sphere. This is a bit tricky, as you have to adjust dPhi based on what latitude it's supposed to be (which is based on Phi...), otherwise you end up with hexagons at the equator and triangles at the poles, or hexagons at the poles and squares at the equator.

It's not linear, either, I derived it to a trigonometric function but didn't bother testing it after I discovered that you could actually do navigation using the above method.