One competition in Croatia

[rsoldo]

Let $A_{1},A_{2},\ldots,A_{2015}$ be vertices of a polygon. Determine the point $T$ in the plane of the polygon so that the sum:

$$|A_{1}T|+|A_{2}T|+\ldots+|A_{2015}T|$$

be the smallest.

[wrest]

for $n=3$:
\
for $n=2015$, one just needs to punch additional $2012$ holes...

[wrest]

add: There's no closed-form expression for $T$, unless $A_i$ of some special type (for example, vertices of regular polygon)

[pogulyat_vyshel]

squares are missed i guess

[ozheredov]

rsoldo в сообщении #1425478 писал(а):

$|A_{1}T|$

What is it? Is this module of a scalar product ($A$ and $T$ are 2D-vectors, right?)

[rsoldo]

Distance from $A_{1}$ to $T$.

[ozheredov]

rsoldo
Oook

[rsoldo]

Hint: complex numbers

[Dendr]

rsoldo в сообщении #1428920 писал(а):

Hint: complex numbers

Complex numbers who?

Basically... Using complex algebra, we just are to find the minimum of complex function $F(z)$, which real part is $\operatorname{Re} F(z)=u(z)=\sum\limits_{i}^{}|z-z_i|$, where $z_i$ are given.

But laplacian of absolute value is its reciprocal, hence it never equals to zero (except for the points about infinity, and we can't talk about minimum there). Thus, it is impossible to find such a real function $v(z)$ so that $\operatorname{Im} F(z)=v(z)$ and $F(z)$ is differentiable at least somewhere.

I don't see if complex algebra made any difference. Worse, maybe - it led to nothing. At least derivation of $f(x,y)=\sum\limits_{i}^{}\sqrt{(x-x_i)^2+(y-y_i)^2}$ gives equations which are numerically solvable.

[svv]

Wiki, Geometric median:

Цитата:

The geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points.
...
Despite the geometric median's being an easy-to-understand concept, computing it poses a challenge. The centroid or center of mass, defined similarly to the geometric median as minimizing the sum of the squares of the distances to each point, can be found by a simple formula — its coordinates are the averages of the coordinates of the points — but it has been shown that no explicit formula, nor an exact algorithm involving only arithmetic operations and kth roots, can exist in general for the geometric median. Therefore, only numerical or symbolic approximations to the solution of this problem are possible under this model of computation.