Minimizing the total distance between points

247 Views Asked by At

Let $P_0, P_1, P_2$ be the vertices of a given triangle. I'm interested in finding $K$ points $P_3, P_4, .... P_{K+2}$ that lie inside the triangle and minimize the total distance given by the expression $\sum_{i=3}^{K+2} \sum_{j=0, j \neq i}^{K+2} (P_i - P_j)^2 $.

This is basically the sum of distances of points $P_3, P_4, .... P_{K+2}$ to all the other points.

When $K = 3$, the solution is the barycenter of the triangle. I'm interested in finding the solution using an analytical approach when $K > 3$.

EDIT: Distance should be $D = \sum_i min_{i\neq j}|| P_i - P_j||^2 $. The objective is to "maximally spread" the points inside the triangle as pointed out in the first answer. For that $D$ has to be maximized.

1

There are 1 best solutions below

1
On

As stated the solution is just placing all points $P_i$ for $i \ge 3$ in the coordinates of barycenter $P_0 + P_1 + P_2 \over 3$.

The problem is more interesting if you want to maximize the sum of distances of each extra point from the set of all other points while keeping all of them inside the triangle (i.e. you want to "maximally spread" them in the triangle).

In other words if you want to maximize

$$ S = \sum_i \min_{i \ne j} \left|P_i - P_j\right|^2 $$

while keeping all points $P_i$ for $i \ge 3$ inside the triangle $P_0, P_1, P_2$.

This problem seems similar to the circle packing problem and therefore I highly doubt there is a known closed form analytical solution (circle packing is a currently open problem even for the simpler case of circles inside a circle).