10
$\begingroup$

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

$\endgroup$
11
  • 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$ Aug 18, 2016 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$ Aug 22, 2016 at 17:44
  • 1
    $\begingroup$ @NateEldredge: The best lowerbound on the number of polygonizations of $n$ points is ~$4.6^n$. $\endgroup$ Aug 26, 2016 at 0:10
  • 1
    $\begingroup$ Well, $4.6^{25}$ isn't that large. $\endgroup$ Aug 26, 2016 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$
    – user44143
    Aug 26, 2016 at 12:03

1 Answer 1

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Do you have reason to believe this is optimal? $\endgroup$ Aug 25, 2016 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$
    – user44143
    Aug 25, 2016 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$ Aug 26, 2016 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$
    – user44143
    Aug 26, 2016 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$ Aug 26, 2016 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.