Published May 19, 2017 | Version v1
Publication Metadata-only

Drawing the double circle on a grid of minimum size

Creators

Contributors

Description

In 1926, Jarník introduced the problem of drawing a convex n-gon with vertices having integer coordinates. He constructed such a drawing in the grid [1, c ·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 of drawing the double circle, and prove that it can be done within the same grid size. Moreover, we give an O(n log n)-time algorithm to construct such a point set.

Abstract

Consejo Nacional de Ciencia y Tecnologia (México)

Abstract

Programa de Apoyo a Proyectos de Investigación e Innovación Tecnológica (Universidad Nacional Autónoma de México)

Abstract

Comisión Nacional de Investigación Científica y Tecnológica (Chile)

Abstract

Fondo Nacional de Desarrollo Científico y Tecnológico (Chile)

Additional details

Identifiers

URL
https://idus.us.es/handle/11441/60117
URN
urn:oai:idus.us.es:11441/60117

Origin repository

Origin repository
USE