# 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

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