# Rule for Finding Largest Possible Perimeter

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

• 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? – Gerry Myerson Aug 18 '16 at 2:21
• 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. – László Kozma Aug 22 '16 at 17:44
• @NateEldredge: The best lowerbound on the number of polygonizations of $n$ points is ~$4.6^n$. – Joseph O'Rourke Aug 26 '16 at 0:10
• Well, $4.6^{25}$ isn't that large. – Nate Eldredge Aug 26 '16 at 1:26
• @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. – Matt F. Aug 26 '16 at 12:03

## 1 Answer

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

• Do you have reason to believe this is optimal? – Nate Eldredge Aug 25 '16 at 20:48
• 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. – Matt F. Aug 25 '16 at 20:56
• 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. – Victor Protsak Aug 26 '16 at 6:11
• @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. – Matt F. Aug 26 '16 at 9:33
• 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. – Victor Protsak Aug 26 '16 at 13:12