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, 2018 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, 2018 at 20:03

2 Answers 2

Reset to default
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, 2018 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, 2018 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .