Some months ago I was given a high-school level maths question that made me wonder if there was a definitive principle for finding the shape of largest perimeter given a set of dots. The question was worded something like the following; Given a 5 by 5 array of points, and using only straight lines, form a polygon with the highest possible perimeter. I understood I would have to use as many and as space-efficient diagonals as possible to maximize my possible perimeter, but couldn't find a rule or certain answer as to the upper bound. So A) What would be the highest possible perimeter shape (I believe I found somewhere around 40, but others found higher) and B) What constant rule can be followed to find the largest possible perimeter for a definite area. I was considering writing a program to brute-force all possible shapes, but wasn't sure if that was even feasible in a reasonable finite time.

EDIT: Polygon must touch all points in the array and can not self-intersect. Sorry for not being clear

  • 1
    $\begingroup$ Does your polygon have to be convex? Does it have to be non-self-intersecting? Have you tried smaller problems, like 2 by 2, 2 by 3, 3 by 3? $\endgroup$ – Gerry Myerson Aug 18 '16 at 2:21
  • 1
    $\begingroup$ For arbitrary point sets in the plane, this sounds like the "longest noncrossing TSP" problem. It was studied by Alon, Rajagopalan, Suri in the paper "Long non-crossing configurations in the plane" who give (IIRC) a constant-approximation. The version with grid points might be easier of course. $\endgroup$ – László Kozma Aug 22 '16 at 17:44
  • 1
    $\begingroup$ @NateEldredge: The best lowerbound on the number of polygonizations of $n$ points is ~$4.6^n$. $\endgroup$ – Joseph O'Rourke Aug 26 '16 at 0:10
  • 1
    $\begingroup$ Well, $4.6^{25}$ isn't that large. $\endgroup$ – Nate Eldredge Aug 26 '16 at 1:26
  • 3
    $\begingroup$ @JosephO'Rourke, minimizing the area will do nothing in this case (!) -- by Pick's theorem, any polygon on these vertices will have an area of 23/2. $\endgroup$ – Matt F. Aug 26 '16 at 12:03

This gives a perimeter of $11 + 3\sqrt{2} + 7\sqrt{5} + 2\sqrt{10} + 2\sqrt{13} \simeq 44.43$. Comfiguration through 5x5 points

  • $\begingroup$ Do you have reason to believe this is optimal? $\endgroup$ – Nate Eldredge Aug 25 '16 at 20:48
  • $\begingroup$ It's the best I found via trial and error. I think sqrt(13) is the longest possible side length, and that there can be at most 2 sides of that length. I'd be interested to see the results of the algorithms in the comments. $\endgroup$ – Matt F. Aug 25 '16 at 20:56
  • $\begingroup$ I don't think sqrt (13) is the longest possible side length - you can start by drawing a diagonal of length sqrt (18) from one of the corners and complete it to a closed circuit, and even include two sides with length sqrt (13) adjacent to it. Of course, the resulting polygon need not be longer overall. $\endgroup$ – Victor Protsak Aug 26 '16 at 6:11
  • $\begingroup$ @VictorProtsak, I would count the diagonal of length sqrt(18) as three sides rather than one, since it goes through the corner plus three other vertices. $\endgroup$ – Matt F. Aug 26 '16 at 9:33
  • $\begingroup$ Fair enough. There are also polygons with three sides of length sqrt (13), although for my best example of this type, the total perimeter, 11+6sqrt (2)+4sqrt (5)+sqrt (10)+3sqrt (13), is less than for the one you have constructed. $\endgroup$ – Victor Protsak Aug 26 '16 at 13:12

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.