# Finding the smallest total sum of differrences

I wanted to find the $k$ so the sum of the differences of $k$ to all elements of a certain set $A$ with size $n$ is minimized. In other words: $\underset{k\in \mathbb C}{\text{minimize }} \sum\limits_i^n k - \lvert A_i \rvert$

For example, if $A = \left\{2,8\right\}$, then $2 \leq k \leq 8$, because no matter what $k$ we choose in that interval, $|k-8| + |k-2| = 6$. In general:

• if $A = \varnothing$, then $k \in \mathbb{Z}$
• if $A$ consists of one element $a$, then $k = a$
• if $A$ consists of two elements $a \leq b$, then $a \leq k \leq b$
• if $A$ consists of more than two elements, just ignore the smallest element and the largest element and re-evaluate

Point 4 works because point 3 tells us that the differences of $k$ with the smallest and the largest elements are minimised as long as $k$ is not smaller than the smallest or larger than the largest, so those two elements can be ignored.

So, when working with single values, this problem is very easy. However, it becomes interesting when working with lattice points in $\mathbb{R}^n$ with $n \in \mathbb{N}_{\geq 2}$. For example, what point $P$ has the smallest sum of the distances to points $(-2,5), (4,1) \text{ and } (-1,-2)$? There are no smallest or largest values to neglect, because each lattice points has multiple values. Of course, a specific problem like this can be solved by asking WolframAlpha to minimise the following equation:

$$\sqrt{(x+2)^2+(y-5)^2} + \sqrt{(x-4)^2+(y-1)^2} + \sqrt{(x+1)^2+(y+2)^2}$$

and it will tell you the optimal lattice point is approximately $(0.549,0.891)$ which is a total of approximately 11.568 away from all three lattice points.

Is this the best we can do? Or is there a more elegant solution, similar to the one for single values rather than lattice points?

-