6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I guess the solution is just the baricenter repeated $K$ times? $\endgroup$
    – Exodd
    Commented Jul 13, 2020 at 19:06
  • $\begingroup$ What do you mean by "repeated K time"? Is it to first find $P_3$ and then compute $P_4$ by getting the barycenter of $P_0, ... P_3$ ? $\endgroup$
    – Optimus
    Commented Jul 13, 2020 at 19:29
  • $\begingroup$ From circle packing, we can say that an approximate solution is a regular triangular grid with all points (including vertices) on grid points, with the triangle covering $K + 2$ grid points. This is not a satisfactory answer, but for numerical approaches (especially if the point locations are e.g. numerically annealed to find a local minimum configuration), it can sometimes be enough. $\endgroup$
    – None
    Commented Jul 13, 2020 at 22:00

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ You have formulated my problem accurately. What I want is to maximally spread the points. $\endgroup$
    – Optimus
    Commented Jul 13, 2020 at 20:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .