Find the minimal possible perimeter of a convex $n$-gon with integer vertices

Question

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$.

.

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

Answer 1

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$.

Answer 2

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}$:

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.