Is there a formula/algorithm/etc. to find the closest equidistant point (assuming it exists) to a set of points, allowing that the number of dimensions of the space is independent of the number of points? Any help would be greatly appreciated.
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ a necessary condition for this to be possible is $N\leq M+1$, if I'm not mistaken; for a sufficient condition you also need to exclude $p+2$ points on a $p$-dimensional subspace (no three points on a line, no four points on a plane, ...); I'm guessing that this special point is the geometric median, for which an efficient algorithm exists. $\endgroup$– Carlo BeenakkerCommented Jan 17, 2022 at 21:52
-
1$\begingroup$ It might not be too big an issue, but "assuming it exists" is doing a lot of heavy lifting for me here. N could be bigger than M... 8 points around a circle in 2-dimensional space have a closest equidistant point. The issue of whether such a point exists for me is only a step to finding what the point is IF it exists. $\endgroup$– ErikCommented Jan 17, 2022 at 22:39
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
If such a point exists, then it is the center of a sphere on which all $N$ points lie, so I think your question is equivalent to asking, do all $N$ points lie on some sphere? Since $M+1$ points determine a sphere in $\mathbb{R}^M$, I think it would be enough to first use $M+1$ points to determine that sphere (for example, as described in a/the answer here: https://math.stackexchange.com/questions/2611326/how-many-points-define-a-sphere-of-unknown-radius), and then check whether the remaining $N-(M+1)$ points are located at the given distance from the given center.
In short: the formula/algorithm merely involves solving a linear system of $M+1$ equations, and then checking distances of the remaining points $N-(M+1)$.
-
$\begingroup$ I like this solution very much for cases where N >= (M+1)! But not sure if I could expand it to cases where N < (M+1)... where there are more than one equidistant points, but one of them is closest? $\endgroup$– ErikCommented Jan 18, 2022 at 18:56
-
$\begingroup$ If three distinct points lie on a line, then no point is equidistant to them. If they don't lie on a line, then a unique circle passes through them; its center is the unique equidistant point. The same is true in general. We need to check that the $N$ points are in "general position", i.e., that they don't lie on a hyperplane of dimension lower than $N-1$. Three points shouldn't lie on a line, four points shouldn't lie in a plane etc. If the $N$ points are in general position, then a unique hypersphere passes through them; its center is the equidistant point. $\endgroup$– MenachemCommented Jan 20, 2022 at 11:02
-
$\begingroup$ More concretely, I think the algorithm referenced above, that involves solving a system of linear equations, will work just as well for the $N < M+1$ case, though the matrix is no longer square. Assuming the system has a solution, then the point $p$ obtained is the center of the (translated) sphere, and hence the equidistant point you seek. $\endgroup$– MenachemCommented Jan 20, 2022 at 11:05
-
$\begingroup$ The algorithm you mention only uses that the distance from your point to the rest of the points is equal, so it will obtain infinitely many solutions if $N<M+1$. This is the case when you are given three non-colinear points in $\mathbb{R}^3$, then there will be a whole line of points at the same distance of the three points. But only one of them is closest to the three points: in this case it can be obtained by intersecting the line of points equidistant to the three given points with the plane containing those points (this is what my answer generalizes). $\endgroup$– Saúl RMCommented Jan 20, 2022 at 22:19
$\begingroup$
$\endgroup$
2
Let $p$ be the closest equidistant point to your set of points, $\{p_1,\dots,p_N\}$. Then $p$ is in the affine subspace $X$ generated by the points: if not, the orthogonal projection of $p$ in $X$ is also at the same distance to all the points and closer to the points than $p$, which is a contradiction.
$p$ is the unique point of $X$ at the same distance from $\{p_1,\dots,p_N\}$: if there was other such point $p'$, then all the $p_i$ would be in the intersection of two spheres of centers $p$ and $p'$, which is impossible because the $p_i$ affinely generate $X$ and the intersection of two distinct spheres in $X$ is always contained in a hyperplane of $X$.
So you can compute $p$ as the intersection of the affine subspace $X$ generated by $p_1,\dots,p_N$ and the bisector hyperplanes $H_{p_1,p_2},H_{p_2,p_3},\dots,H_{p_{n-1},p_N}$. Moreover, if your set of points is not affinely independent, you can change it by a maximal affinely independent subset. All of this assuming the existence of $p$, of course.
-
$\begingroup$ Thank you! I'm sorry this explanation is a bit beyond my current math knowledge to know how to evaluate or implement. I'll do some research. $\endgroup$– ErikCommented Jan 18, 2022 at 19:01
-
$\begingroup$ Okey. I suppose you have some program to calculate intersections of hyperplanes (?), so would the problem be obtaining the equations of the affine subspace generated by the points? $\endgroup$– Saúl RMCommented Jan 18, 2022 at 19:22
$\begingroup$
$\endgroup$
An algorithm that works at least for dimensions $2$ and $3$ is:
- calculate a spanning tree of the $n$ points
- calculate the bisector planes of the spanning tree's edges
- the sought poiint is in the intersection of the affine subspace defined by the intersection of the bisector planes and has least distance to any of the given ones.
that algorithm can be generalized to arbitrary many points by taking the least squares solution to the intersection of the bisector planes with the subspace that is orthogonal to these intersections and contains the $n$ points.
For numerical reasons the maximum weight spanning tree seems preferable over the minimum weight spanning tree; it is also recommended to move the $n$ points center of gravity to the origin to prior to the calculations.
answered Jan 18, 2022 at 4:44