pith. sign in

arxiv: 1305.6693 · v1 · pith:6LFZ52D2new · submitted 2013-05-29 · 💻 cs.CG · math.CO

Drawing the double circle on a grid of minimum size

classification 💻 cs.CG math.CO
keywords drawinggridsizecircleconstantdoubleproblemalgorithm
0
0 comments X
read the original abstract

In 1926, Jarn\'ik introduced the problem of drawing a convex $n$-gon with vertices having integer coordinates. He constructed such a drawing in the grid $[1,c\cdot n^{3/2}]^2$ for some constant $c>0$, and showed that this grid size is optimal up to a constant factor. We consider the analogous problem for drawing the double circle, and prove that it can be done within the same grid size. Moreover, we give an O(n)-time algorithm to construct such a point set.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.