Suppose I want to construct an $N$-gon in the plane whose vertices are integer lattice points, and which is close to a regular $N$-gon (which means, the ratio of longest to the shortest side is within $\epsilon\_1$ of $1,$ and the ratio of the largest to the smallest angle is within $\epsilon\_2$ of $1$) The question is: is there any sort of reasonable upper/lower bound to the size (area or diameter) of such a thing? This is clearly related to diophantine approximation in the following way: take the "standard" regular $N$-gon (one whose vertices are $N$-th roots of unity,) and blow it up by a factor of $t$ until wall the vertices ($t$ times the roots of unity) are close to lattice points. How big does $t$ need to be in terms of some "closeness" bound?



Regular lattice polygons
Probably [Dirichlet's approximation theorem](http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) gives best possible answer for large $N$. We can only reduce the number of simultaneous approximations using symmetries of $N$-gon. For example for $8$-gon it is necessary to approximate only one number $1/\sqrt2$ among $8$ numbers $e^{2\pi ik/8}$ $(k=0,\ldots 7)$. 


But starting from arbitrary $N$-gon inscribed into the unit circle we can find $t\le R$ such that 
$$|tx\_1-a\_1|\le\frac1{R^{\frac1{2N}}},|ty\_1-b\_1|\le\frac1{R^{\frac1{2N}}},\ldots |tx\_N-a\_N|\le\frac1{R^{\frac1{2N}}},|ty\_N-b\_N|\le\frac1{R^{\frac1{2N}}},$$
where $(x\_1,y\_1), \ldots, (x\_N,y\_N)$ are coordinates of initial $N$-gon. It means that we can achieve $\epsilon\_1=\epsilon\_2\asymp t^{-1-\frac1{2N}}$ in the circle of radius $t$ for infinitely many $t$.


If we want a better exponent, we can do the following. For arbitrary $N$ we can take $x\_1=1$, $y\_1=0$ (no approximation needed). The rest part of vertices is symmetrical. So for odd $N$ we need to approximate $(N-1)/2$ points ($N-1$ coordinates), for $N\equiv2\pmod4$ $(N-2)/4$ points ($(N-2)/2$ coordinates), for $N\equiv4\pmod8$ $(N-4)/8$ points, for $N\equiv0\pmod8$ $(N-2)/4$ points $1+(N-8)/8$ coordinates.


Also there is an algorithm (based on discrete Fourier transform) of complexity $O(t^2)$ which allows to find all best possible solutions in the circle of radius $t$. This algorithm was published in [Algebra and number theory for mathematical schools. Collected problems](http://iam.khv.ru/articles/Ustinov/emath23.pdf) (Russian, see page 138). 


It is very simple. We need so specify only one vertex to define our regular $N$-gon. So we take all points $A\_1=(x\_1,y\_1)$ such that $0\le y\_1\le x\_1\le t$. For each $A\_1$ we define $A\_2',\ldots,A\_N'$ rotating $A\_1$ around the origin, and $A\_2,\ldots,A\_N$ as nearest integer points to $A\_2',\ldots,A\_N'$. After that it necessary to check the quality of resulting $N$-gon. We can say that $A\_1,\ldots,A\_N$ are $N$ complex numbers and calculate discrete Fourier series. First Fourier coefficient gives main cycle ($|C\_1|\approx |OA\_1|$) and the rest part of Fourier series forms an error term.


