EMBEDDING THE DOUBLE CIRCLE IN A SQUARE GRID OF MINIMUM SIZE
Sergey Bereg, Ruy Fabila‐Monroy, David Flores‐Peñaloza, Mario Alberto Lopez, Pablo Pérez-Lantero · International Journal of Computational Geometry & Applications · 2014
In 1926, Jarník investigated the drawing of a curve that visits a large number of lattice points relative to its curvature. To this end, he constructed a convex n-gon with vertices on a “small” integer grid [0, c.n3/2]2, where c > 0 is a constant, and proved that this grid size is optimal up to a constant factor. We consider a similar construction for the double circle of 2n points and prove that it can be embedded in a grid of the same asymptotic size. Moreover, we give an O(n)-time algorithm to generate the corresponding point set.