# Minimum distance to points in plane

Someone told me that the the following problem is elementary. Given three points $a=(-5,0)$, $b=(0,5)$ and $c=(5,0)$ in $\mathbb R^2$ with Euclidean norm:

$$\mbox{minimize}\;\; \; f(x)=\|x-a\| + \|x-b\|-2\|x-c\|,\;\; x\in \mathbb R^2.$$

-
I'll give you 2 hints: - first, minimizing $(x-a)^2$ is equivalent to minimizing $\sqrt{(x-a)^2}$. Of course the minimum value will be different, but the location will be the same. - Now just think, how would you find the minimum to a generic function $f_{(x)}$? And if it were $f_{(x,y)}$? – Steve Heim Mar 31 '14 at 13:15
@lifesayko: I don't know how to use your hints at all! Hic, please make it more clearly. – Richkent Mar 31 '14 at 14:21
Richkent, it is not my job to solve your your probelms for you. Please show at least what you've tried. What specifically are you having trouble with? Show how you would set up the problem. If you really have no idea, try to find the minimum to a generic problem $f_{(x)}$, such as $f_{(x)}=x^2+4$. Then reason how to transfer this to what you have. – Steve Heim Apr 1 '14 at 11:38
Fist of all, I want to verify that whether the problem has a global minimum or not? I have showed that $f(x)$ is bounded but the existence of a minimum point have been not determined yet. – Richkent Apr 1 '14 at 12:38
I have no solution, but the - not elementary - problem seems to be the "Fermat Weber Problem with positive and negative weights". Your constellation looks asymptotically bounded at $f(x)=-\sqrt{250}$ for $x=(t, -t/3) \text{ for } t \to -\infty$. – Axel Kemper Apr 1 '14 at 21:41

You seem to be serious about solving this problem. What I would try is this: Choose any $r$ such that $$\|a-b\| \le r < \infty.$$ Consider the ellipse $$\|x-a\|+\|x-b\|=r,$$ for which you can get an equation by the standard trick of expanding: $$\|x-a\|^{2}=r^{2}-2\|x-b\|+\|x-b\|^{2} \\ \|x-a\|^{2}-\|x-b\|^{2}-r^{2}=-2\|x-b\| \\ (2(b\cdot x)-2(a\cdot x)+\|a\|^{2}-\|b\|^{2}-r^{2})^{2}=4\|x-b\|^{2}.$$ ("$\cdot$" represents vector dot product in the last expression.) Now, minimize $f$ on this ellipse. This comes down to considering $f(x)=r-2\|x-c\|$ for $x$ on the ellipse. Finally, look at the minimum value of $f$ as a function of $r$, and see what you can do with that.
Note: Try finding the location of the minimum for $f(x)=r-2\|x-c\|$ on the ellipse by finding the location of the maximum for $\|x-c\|^{2}=\|x\|^{2}-2(x\cdot x)+\|c\|^{2}$ on the ellipse, which can be done by first replacing $\|x\|^{2}=x_{1}^{2}+x_{2}^{2}$ with terms from the equation for the ellipse.
No guarantee that this will lead to enough reduction in complexity, but I don't see any other reasonable suggestions. It might be worthwhile to first rotate the configuration until $a$ and $b$ are on one horizontal or on one vertical line.