1
$\begingroup$

How would I go about selecting $3$ random points $p$, $q$, and $r$ on the perimeter of a square of side a such that they are as far apart from each other as possible (i.e. the sum of the euclidean distances from $p$ to $q$, $q$ to $r$, and $p$ to $r$ is maximized)?

Is there a general method to do this such that I can extend it to (for example) finding $5$ such points on the surface of a cube of side $a$? $7$ on the surface of a sphere of radius $a$? Not a textbook problem, was just thinking for fun and got lost.

Can try solving the square problem with a simulation on a computer, but looking for mathematical insight. Thank you.

$\endgroup$
4
  • $\begingroup$ These are similar to packing problems, which are hard. For a given general configuration, you can take the derivative of your objective with respect to the positions of the points and find a local optimum. Unfortunately, there may be a better general configuration. For small numbers of points you can justify that you have tried all the configurations or can rule out some of them. For three points on a square, they should clearly all be on different sides. Then the two that are next to a side with no points should be at the corners away from the side with a point, and that point should $\endgroup$ – Ross Millikan May 16 '20 at 4:23
  • $\begingroup$ at the center. For seven on a sphere, you can imagine a point at a pole with two sets of three on lines of latitude. Are you sure that is the best configuration? If you look at packomania you will find different packing problems that surprisingly often have asymmetric arrangements that are superior to symmetric ones. $\endgroup$ – Ross Millikan May 16 '20 at 4:26
  • $\begingroup$ @RossMillikan, for three points in a square, it sounds like you are suggesting that $(1+\sqrt 5)a$ is optimal. But putting the three points in three corners instead yields the larger sum of distances $(2+\sqrt 2)a$. $\endgroup$ – RobPratt May 16 '20 at 15:49
  • $\begingroup$ Are you trying to maximize the sum of the distances, or maximize the minimum distance? $\endgroup$ – Mark L. Stone May 17 '20 at 13:55
2
$\begingroup$

For $i\in\{1,2,3\}$, let $(x_i,y_i)$ denote the coordinates of point $i$. The problem is to maximize $\sum_{1\le i<j\le 3} \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$ subject to bound constraints: \begin{align} 0\le x_i &\le a \\ 0\le y_i &\le a \end{align} Now use multivariable calculus. An optimal solution will naturally occur on the boundary.

$\endgroup$
1
  • $\begingroup$ @genokem, the perimeter of inscribed triangle is maximum if two side are coincident with two sides of square and third side is the diameter of the square. $\endgroup$ – sirous May 16 '20 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.