I was trying to maximize the distance between points on a triangle for a program the other day. Snooping around led me to the circle packing problem. However, the circle packing problem assumes that you also want to maximize distance from the borders. What if you can also place your points ON the triangle? I've been trying to figure it out by projecting onto the triangle and using calculus but that gets really nasty. Is there a geometric way to do it? Solutions for 2, 3, 4, and 6 points are pretty obvious, but I can't figure out the rest.

For example, this haphazardly drawn sketch would be the way to optimize 4.enter image description here

In other words: how can we maximize the pairwise distance of points placed on or within an equilateral triangle? Can we extend this problem to other polygons?

Also, we're looking to make them both as equidistant and as maximized as possible. I'm not really certain how we could measure this, but the problem would be trivialized if we just stuck all of them into one corner and put the other one in an opposite corner. I guess the problem might be better worded as "find the distance c for which n points in or on an equilateral triangle cannot be placed without having at least one pair of points be at most c apart."

  • $\begingroup$ your title says excluding borders, your questions states points ON the triangle. Furthermore, as you talk about more than 2 points, please elaborate on what distance you want to maximize. $\endgroup$ – Eric S. Mar 3 '16 at 15:07
  • $\begingroup$ Perhaps if you showed pictures of your solutions for small cases we'd be able to figure out what problem you're trying to solve. $\endgroup$ – Ethan Bolker Mar 3 '16 at 15:11
  • $\begingroup$ Oh sorry, that's a mistake. INCLUDING borders is what I want. $\endgroup$ – user319608 Mar 3 '16 at 15:12
  • 1
    $\begingroup$ If I understand correctly - you want to place $n$ points in an equilateral triangle so as to minimize the sum of the pairwise distances. If that's right, please edit the question accordingly. My guess is that there's no clean answer. We'll see. $\endgroup$ – Ethan Bolker Mar 3 '16 at 15:29
  • 1
    $\begingroup$ Yeah, now that you've made me think about it, the problem gets much messier, even with wording. I've modified the problem a little bit. $\endgroup$ – user319608 Mar 3 '16 at 15:35

Border or not, these two problems are equivalent, similar to what I showed here for squares. The relation between s and d is $d=\frac2{s-2\sqrt3}$. So you're better off looking up known circle packings and converting them to point distributions.


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.