0
$\begingroup$

Given $n$ points in $\mathbb{R}^3$, the most exactly equidistant points we can have is $n=4$. I was wondering for larger cases how to construct the closest possible situation to having all points equidistant. I was thinking of maybe having one point be the center of a sphere, and then the other points being on the surface of the sphere and being approximately mutually equidistant from each other. I'm not sure if this is the right idea, but even if it is I'm not sure exactly how to execute it. Any help would be appreciated.

$\endgroup$
  • $\begingroup$ My first intuition is probably an ugly one one to implement, but here it is. You're looking to minimize the sum of the pairwise distances between each of your points. So, calculate the n choose 2 distances as a formula in n variables (each 3 dimensional, so more like 3n), then minimize that function. Have fun! :). I'm sure there's a better approach $\endgroup$ – Alan Apr 25 at 20:38
  • 2
    $\begingroup$ The approach you mention for scattering them on the surface of a sphere can work (approximately) for each point to be the same distance from its neighbors. You will still have pairs of points the diameter of the sphere apart. An example would be the $20$ points of an icosohedron. Maybe you would prefer distributing them in volume, which can reduce the discrepancy between maximum and minimum distances. You need to specify what you want. Then it becomes a packing problem and those are hard. $\endgroup$ – Ross Millikan Apr 25 at 20:42
  • $\begingroup$ @RossMillikan To specify, I was either thinking of having all points satisfying $d-\epsilon \leq \|x_i-x_j\|\leq d+\epsilon$ or having most points satisfying that property for a smaller $\epsilon$ and then a couple points can be further away $\endgroup$ – user655866 Apr 25 at 20:46
  • $\begingroup$ @Alan So like minimizing $\sum_{i\neq j} (\|x_i-x_j\|-d)$? $\endgroup$ – user655866 Apr 25 at 20:51
  • $\begingroup$ @user655866 Yep. $\endgroup$ – Alan Apr 28 at 3:47
0
$\begingroup$

I do not think, that I understand your problem yet but I'm going to give it a try. But first, let us verify a bunch of stuff. Let $P^{(1)},\dots,P^{(n)} \in \mathbb{R}^3$

  • What do you mean with distant? Assuming it would be the standard metric in $\mathbb{R}^3$, then let denote it by $$ \left\lVert P^{(i)} - P^{(j)}\right\rVert = \sqrt{x^{(i)}x^{(j)} + y^{(i)}y^{(j)}+ z^{(i)}z^{(j)}} \qquad \text{ where } x,y,z \in \mathbb{R} \qquad \text{ for } i,j = 1,\dots, n$$
  • What do you mean by equidistant? Does it mean - for some constant $c \in \mathbb{R}$ $$ \left\lVert P^{(i)} - P^{(j)}\right\rVert = c \qquad \forall i,j = 1, \dots n $$ If this is the case. Then with $n = 2$ the points will make a segment, $n =3$ is a quilateral triangle and $n = 4$ is a triangular pyramid with all equilateral triangle. We can think of a way to generalize this for the case $\mathbb{R}^d$ by elaborating about the construction of equaliteral triangle but not with the sphere. The reason we can't use a sphere is, because the diameter is always twice the radius, thus any two points lying opposite to each other always have a greater distance than that towards their neighbor. Instead one can guesses, that the figure as the result of the complete graph from all these points, may be shaped by a bunch of equiliteral triangles.
$\endgroup$
  • $\begingroup$ Yeah, this is pretty much what I was asking in the question. So are you saying to just put a bunch of equilateral triangles together for larger cases? $\endgroup$ – user655866 Apr 25 at 21:46
  • $\begingroup$ It is but an intuition. Since we have to generalize and define the concept of "just put a bunch of equilateral triangles together", which is not easy to achieve. To begin with, you cannot even imagine such a shape in $\mathbb{R}^4$ anymore. So you have to seriously put your hand deep in geometry (especially complex projective geometry). $\endgroup$ – Hirosanza Apr 25 at 22:03
0
$\begingroup$

Probably the simplest approach is to place your points in a hexagonal close packed array with outer envelope about a sphere. It is like the centers of a bunch of tightly packed spheres. Each point is the same distance from its neighbors and roughly speaking the maximum distance between any two points is the diameter of the sphere. I suspect this is about the best you can do if your criterion is the ratio of maximum to minimum distance. For small numbers of points there will be perturbations. Packing problems are hard.

$\endgroup$
0
$\begingroup$

One sensible way to interpret your question is given $n$ points in the plane, what is the maximum number of pairs of points with distance between $d-\varepsilon$ and $d+\varepsilon$ between them? For $\varepsilon =0$ this is some discrete geometry problem that I would not know how to solve. But for $\varepsilon > 0$, I present the following possibly tight construction. Simply place four tight groups of points of size $n/4$ on the four vertices of a regular tetrahedron. Then $3/4$ of the pairs have the desired distance.

$\endgroup$

Your Answer

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