1
$\begingroup$

Let the smallest distance between $m$ points in a regular $n$-gon be denoted by $D$. Is there a general formula for $D_{\mathrm{max}}$? In other words, how should $m$ points be placed so that they are all spread as far apart as possible. For example, for a triangle and $m \leq 3$ we would place all the points on the vertices. This can be extended to any $n$-gon: place $m \leq n$ points on all the vertices. Then I imagine the $(n+1)$-th point should be placed in the center. From there I don't know if it should be on the midpoint of the edges or somewhere in the middle of the shape.

I don't know if this has an answer (maybe it is more simple than I think), I just saw a similar question and was curious if it could be generalized.

$\endgroup$
  • $\begingroup$ Could you share a link to this similar question you mentioned? $\endgroup$ – Glinka Jan 22 '17 at 18:32
  • $\begingroup$ [link] (quora.com/…) is the general idea. $\endgroup$ – user20354139 Jan 22 '17 at 18:35
  • $\begingroup$ Packing problems are hard. You could look at Packomania to see what strange configurations are optimal. $\endgroup$ – Ross Millikan Jan 22 '17 at 18:38
2
$\begingroup$

Instead of having points at distance $D$ or more from each other, you might also consider disks of radius $\frac D2$ that don't overlap. Having the points inside a regular polygon means having the disk centers in that polygon, which in turn means having the whole disks in a polygon which is a larger copy of the original, with the edges moved $\frac D2$ to the outside. Instead of asking to maximize $D$ for a given number of points and a given $n$-gon you can also keep $D=1$ and ask for the smallest $n$-gon containing this many unit disks. So now you are in the realm of packing a regular polygon with disks. Which is a hard problem.

Erich's Packing Center lists a few of these: disks in triangles, squares, pentagons and hexagons. Observe how there is no simple formula describing all of these cases, but each combination $(m,n)$ is described individually. Observe how many of the configurations look far from regular. Also observe the distinction between “Proved by …” and “Found by …”. The latter usually describe the best known solution, but no known proof of optimality. At the time of writing, but even if some of these might have been proven by now, the general message of “this is really hard” still holds.

$\endgroup$
  • 1
    $\begingroup$ The $(3,4)$ case is a counterexample to one of the conjectures in the question: "place $m≤n$ points on all the vertices". However the other conjecture, "the $(n+1)$-th point should be placed in the center", does seem to hold. $\endgroup$ – Rahul Jan 23 '17 at 14:57

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.