3
$\begingroup$

Given an arbitrary set of points on a Cartesian coordinate plane, is there a generalized formula to find the closest point that is equidistant from all the given points?

My first guess was finding the centroid, which is fairly easy to calculate, but the centroid of a polygon isn't equidistant from all its vertices.

$\endgroup$
  • 2
    $\begingroup$ Consider the points (0,0), (1,1), (2,2), in the plane. No point is equidistant from these points. Have I missed something in the definitions? $\endgroup$ – utdiscant Apr 11 '12 at 18:14
  • $\begingroup$ For an arbitrary set of points, it may not exist... $\endgroup$ – Sasha Apr 11 '12 at 18:14
  • $\begingroup$ It is not clear to me what the point should do. Should it minimize the maximum distance? $\endgroup$ – André Nicolas Apr 11 '12 at 18:15
  • $\begingroup$ So given some $\epsilon \gt 0$ and points $P_1, P_2, \dots P_n$, you want a point $P_{\epsilon}$ such that $|D(P_{\epsilon},P_i) - D(P_{\epsilon},P_j)| \lt \epsilon$, if it exists and then try to "minimize" $\epsilon$ and find a corresponding $P_{\epsilon}$? $\endgroup$ – Aryabhata Apr 11 '12 at 18:16
  • $\begingroup$ Ah, I see. I didn't realize that it could be impossible to find an equidistant point... Aryabhata, that sounds about right. $\endgroup$ – kennysong Apr 11 '12 at 18:16
8
$\begingroup$

There is no point that is equidistant from 4 or more points in general position in the plane, or $n+2$ points in $n$ dimensions.

Criteria for representing a collection of points by one point are considered in statistics, machine learning, and computer science. The centroid is the optimal choice in the least-squares sense, but there are many other possibilities.

Added to answer the comment:

The centroid is the point $C$ in the the plane for which the sum of squared distances $\sum |CP_i|^2$ is minimum. One could also optimize a different measure of centrality, or insist that the representative be one of the points (such as a graph-theoretic center of a weighted spanning tree), or assign weights to the points in some fashion and take the centroid of those.

$\endgroup$
  • $\begingroup$ What does "least-squares" mean? And what are some alternatives to the centroid? $\endgroup$ – kennysong Apr 12 '12 at 3:17
  • $\begingroup$ I updated the answer. $\endgroup$ – zyx Apr 12 '12 at 4:28
0
$\begingroup$

Given that the question asks for a method to find a point equidistant to a given set of points and the accepted answer claims that the centroid provides the answer in the "least-squares sense", it seems appropriate to present the actual least-squares solution.

Let the cost-function be: $$ \tilde{y}_i = \lvert\lvert x_i-\hat{x}_c\rvert\rvert_2 - \hat{r}_c $$ Where $x_i$ is the Cartesian coordinate of the $i^{th}$ point in the set, $\hat{x}_c$ is the estimated "equidistant center", and $\hat{r}_c$ is the estimated distance between $\hat{x}_c$ and all other points $x_i$.

The Jacobian of $\tilde{y}_i$ with respect to the desired state $\begin{bmatrix} \hat{x}_c \\ \hat{r}_c \end{bmatrix}$ is: $$ H_{i,12} = -\frac{(x_i - \hat{x}_c)}{\lvert\lvert x_i - \hat{x}_c\rvert\rvert_2} $$

$$ H_{i,3} = -1 $$

Where $H$ is a $N_p \times 3$ matrix ($N_p$ is the number of 2D Cartesian points), $H_{i,12}$ is the first two columns of the $i^{th}$ row, and $H_{i,3}$ is the third column of the $i^{th}$ row.

Let: $$ \hat{\mathbf{x}} = \begin{bmatrix} \hat{x}_c \\ \hat{r}_c \\ \end{bmatrix} $$ be the stacked state vector. A single least-squares update looks like:

$$ \hat{\mathbf{x}}_{k+1} = \hat{\mathbf{x}}_k - (H^T H)^{-1} H^T \tilde{y} $$

The least-squares estimate to the question can be calculated by initializing $\mathbf{x}_{k=0}$ with an initial guess (perhaps involving the centroid) and iteratively updating $\tilde{y}$ and $\hat{\mathbf{x}}$.

This is the answer in the least-squares sense.

This set of 6 points:

$x = \lbrace[443.292, 397.164], [355.53, 349.168], [326.975, 253.249], [562.139, 186.385], [375.017, 165.456], [473.424, 137.604]\rbrace$

has a ``least-squares equidistant center'' of $[457.9097, 267.1183]$ with a point separation of $131.1977$.

Note that the given points are 6 of 8 equally spaced points around a circle (i.e., 2 are missing) and the least-squares solution recovers both the center of the circle and its radius.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.