2
$\begingroup$

We want to mimimize the sum of distances from $n$ distinct points. Prove that there exists only one such point for $n>3$ if all the $n$ points lie on a single plane (and not on a single line)

The problem seems quite tough, but might possess an elegant solution. I tried creating two PDE's (partial differential equations) for $x$ and $y$ coordinates and couldn't find anything fruitful. Might be something towards vectors and their sum.

$\endgroup$
  • $\begingroup$ Would you care to explain the statement ''Prove that there exists only one such point for n>3 on a single plane.'' It is not clear to me what you mean. You could minimize the sum of those distances, but the unclear part is ''on a single plane'' $\endgroup$ – John D Nov 2 '17 at 10:38
  • $\begingroup$ @Magnusseen i meant all points lie on a single plane $\endgroup$ – avz2611 Nov 2 '17 at 10:40
  • $\begingroup$ @JohnWatson Partial Differential Equations $\endgroup$ – avz2611 Nov 2 '17 at 10:40
  • 2
    $\begingroup$ I think some confusion is created by the wording, hence the questions. But as I understand it, you are given a fixed number of points, say $k$, on a plane and you seek to show that there exists a unique point on the plane, different from these $k$ points, such that the distance of it from all these $k$ points is minimum. $\endgroup$ – MathematicianByMistake Nov 2 '17 at 10:46
  • 1
    $\begingroup$ Glad to clarify. I suggest you edit because it seems-to me at least-as a very nice problem. +1 $\endgroup$ – MathematicianByMistake Nov 2 '17 at 10:49
2
$\begingroup$

lemma:suppose $A,B,C$ are three distinic points on plane , and $M$ is the middle point of $BC$, then $AM \le {{AB+AC} \over 2} $

proof:

if three points $A,B,C$ lie on a line it is clear the condtion is true, now consider the case which three point create a triangle , suppose $A_1$ be the symmetry point of $A$ into $M$ then quadrilateral $ABA_1C$ diameters , cuting each other in to half , so it is a parallelogram.please note that $AA_1=2AM$ and $AB=CA_1$ now accordin to the triangle inequality in the $AA_1C$ we have $AA_1 <AC+CA_1$ thus $2AM<AB+AC$ and it is proved.

now lets solve problem using this lemma:

suppose ${A_1,A_2,A_3,....,A_n}$ are $n$ distinic point and suppose there exist two point that has minimumthe sum of distances from $n$ distinct points, call them $X$ and $Y$.

call the middle point of $X$ and $Y$ the $M$,now we are using above lemma in $A_1XY$ and $A_2XY$ and ... $A_nXY$ (please note that even if three point lies on a line then lemma is true):

$A_1M \le {{A_1X+A_1Y}\over 2}$

$A_2M \le {{A_2X+A_2Y}\over 2}$

.....

$A_nM \le {{A_nX+A_nY}\over 2}$

add all of them ,$A_1M+A_2M+...+A_nM \le { {A_1X+...+A_nX+A_1Y+...+A_nY} \over 2}$ but since all the points is not on a single line so at least one of the inequalitys is strict inequality thus $A_1M+A_2M+...+A_nM < { {A_1X+...+A_nX+A_1Y+...+A_nY} \over 2}$, and since $X$ and $Y$ has minimum sum,call it H, so $A_1M+A_2M+...+A_nM < H={2H\over 2}={ {A_1X+...+A_nX+A_1Y+...+A_nY} \over 2}$ so the point $M$ is the desired point which is contradiction.(note you should add all the point is not on a single line other wisee there exist two points)

$\endgroup$
  • $\begingroup$ Oh my goodness i forgot to mention that thanks for mentioning this! $\endgroup$ – avz2611 Nov 2 '17 at 11:39
  • $\begingroup$ i really like this solution, clean and simple to understand +1! $\endgroup$ – avz2611 Nov 2 '17 at 14:33
5
$\begingroup$

Hints & References

You are seeking to prove that the Geometric median is unique. This holds true only if the points are not colinear, an assumption that should be added at the description.

This paper-"The multivariate L1-median and associated data depth"-presents a generalized approach.

This answer on-"How to find out Geometric Median" on stackoverflow provides an algorithm for finding such a point.

Also this post-"Geometric median (or Fermat-Weber problem), including continuous case"-here on MSE might interest you-

$\endgroup$
0
$\begingroup$

Here is your sum $$ S(r) = \sum_{k=1}^n \lVert r - r_k \rVert $$ where $r, r_k \in \mathbb{R}^N$. The $i$-th component of the $r$-gradient of $S$ in the Euclidean norm is \begin{align} \partial_i S(r) &= \partial_i \sum_{k=1}^n \lVert r - r_k \rVert \\ &= \partial_i \sum_{k=1}^n \sqrt{\sum_{j=1}^N \left(x_j - x_{k,j} \right)^2} \\ &= \sum_{k=1}^n \frac{1}{2}\lVert r - r_k \rVert^{-1} \sum_{j=1}^N 2(x_j-x_{j,k})\delta_{ij} \\ &= \sum_{k=1}^n \frac{x_i-x_{k,i}}{\lVert r - r_k \rVert} \end{align} So critical points $r$ of $S$ (which are candidates for extrema) fulfill the condition $$ \sum_{k=1}^n \frac{r-r_k}{\lVert r - r_k \rVert} = 0 $$ This seems to be the characterization of the geometric median (Wikipedia article).

The Wikipedia article links to Vardi & Zhang (2000) for a uniqueness proof, which was already cited by MathematicianByMistake.

$\endgroup$
  • $\begingroup$ I dont get it why does this prove uniqueness $\endgroup$ – avz2611 Nov 2 '17 at 11:36
  • $\begingroup$ It does not. It just provides the starting point, why one lands at the geometric median $\endgroup$ – mvw Nov 2 '17 at 13:04
0
$\begingroup$

Suppose the minimum sum occurs at two points, $P$ and $Q$. Let $M$ be the midpoint of the line segment $PQ$. For all points not on the line $PQ$, the distance to $M$ is strictly less than the average of the distance to $P$ and $Q$. Since it's assumed that not all $n$ points are on a single line, the sum of their distances to $M$ is strictly less than the average of their sums to $P$ and $Q$ -- which is to say, strictly less than the minimum sum. That's a contradiction, hence the mimimum sum occurs at a unique point.

Remark: As Nick Pavlov points out, this answer essentially duplicates Dexpectra's. That answer contains a nice proof of the key observation, that the distance to $M$ is less than the average of the distances to $P$ and $Q$ (by viewing $M$ as the center of a parallelogram with $P$ and $Q$ as oppositve vertices).

$\endgroup$
  • $\begingroup$ this might be worded more succinctly than Dexpectra's answer, but is otherwise exactly the same; perhaps we need a [duplicate] flag for answers now, too. $\endgroup$ – Nick Pavlov Nov 2 '17 at 12:28
  • $\begingroup$ @NickPavlov, I have to admit, I glanced at Dexpectra's answer but didn't read it. $\endgroup$ – Barry Cipra Nov 2 '17 at 12:31

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.