4
$\begingroup$

Find the minimal possible perimeter of a convex $n$-gon with vertices at points with integer coordinates. The polygon must have interior angles less than $180$ degrees.

It is guaranteed that $n$ is even. For $n = 4$ the output should be $4$.

It is optimal do a square with side length $1$ in this test.

For $n = 10$ the output should be $14.12899$.

enter image description here.

This is an example of a convex $10$-sided polygon with minimal perimeter (with vertices at integer coordinates). It has four sides of length $1$, four sides of length $\sqrt{2}$, and two sides of length $\sqrt{5}$, for a total of about $14.12899$. What is the formula?

Source:https://codefights.com/signup/DTAhxMpk5eXTjAtYo/main

$\endgroup$
2
  • $\begingroup$ Could you visuallize it when n=6 and n=8 joriki! $\endgroup$ – The moon Jun 5 '18 at 12:07
  • $\begingroup$ I guess that as always is asked to OP you should show what you have tried yet. You just copied the problem and image from a challenge from code fights (codefights.com/challenge/bfXbznXk7oHMD7Ddv). Dont know what are the policies about this situations, but at least I´ll try the answer the questions at least once the challenge is finished. $\endgroup$ – Dimitri Jun 5 '18 at 20:03
5
$\begingroup$

Each edge corresponds to a point in $\mathbb Z^2\setminus\{0\}$. (To visualize this, pick an orientation, traverse the polygon and for each edge, shift the initial vertex to the origin and mark the final vertex with a dot.)

The contribution of an edge to the perimeter is the distance of the corresponding point in $\mathbb Z^2\setminus\{0\}$ from the origin. You can't use the same point twice (since that would produce an "angle of $\pi$" that the question disallows). So just add up the distances from the origin to the closest $n$ points in $\mathbb Z$.

$\endgroup$
2
  • 1
    $\begingroup$ Closest $n$ points? I think you cannot have both $(1,0)$ and $(2,0)$. So I think you want the closest $n$ points "visible from the origin". (But also, the closest $3$ points give you total $3$ but you should get $2+\sqrt{2}$. Your points have to add to $(0,0)$. Only an objection for $n$ odd) $\endgroup$ – GEdgar Jun 5 '18 at 12:29
  • $\begingroup$ Both good points. You've already said how to fix the first mistake. As for the second, for even $n$, you can make the points add to $(0,0)$ by always choosing opposite pairs when you have more than $2$ points to choose from. For odd $n$ I don't have an idea off the top of my head how to optimize the sum under that constraint. $\endgroup$ – joriki Jun 5 '18 at 12:33
1
$\begingroup$

comment
I hope the OP does not mind if we discuss $n$ odd as well.

Call the points in joriki's answer the edge vectors. When $n$ is odd, perhaps we cannot choose the $n$ points nearest the origin visible from the origin as the edge vectors, since they may not add to $(0,0)$.

Can we get the least perimeter by choosing the nearest $n-1$ points and then using the last point to get sum $(0,0)$? No, when $n=5$, the $4$ nearest points already have sum zero. So we can have at most $3$ edge vectors of length $1$.

Perhaps that does work for $n=11$. Anyway, here is an $11$-gon with perimeter $4+4\sqrt{2}+2\sqrt{5}+\sqrt{10}$:

11-gon

Is that the minimum for $n=11$? The edge vectors are $$ (1, 0) , (2, 1) , (1, 1) , (0, 1) , (-1, 2) , (-1, 1) , (-1, 0) , (-1, -1) , (-1, -3) , (0, -1) , (1, -1) $$ Is it clear that for the minimum perimeter we must use all of the edge vectors of length $1$ and all of the edge vectors of length $\sqrt{2}$?

Is it clear in general that a minimum configuration with $n$ odd cannot use edge vector $(2,0)$ but not $(1,0)$?


Let me add $n=6$ and $n=8$ according to joriki's method, as requested by moon.

hexagon

octagon

$\endgroup$

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.