Ponencia
Drawing the double circle on a grid of minimum size
Autor/es | Bereg, Sergey
Fabila Monroy, Ruy Flores Peñaloza, David Lopez, Mario A. Pérez Lantero, Pablo |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-05-19 |
Publicado en |
|
Resumen | 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 ... 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. |
Identificador del proyecto | 153984
168277 IA102513 11110069 |
Cita | Bereg, S., Fabila Monroy, R., Flores Peñaloza, D., Lopez, M.A. y Pérez Lantero, P. (2013). Drawing the double circle on a grid of minimum size. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Drawing the double circle on a ... | 988.6Kb | [PDF] | Ver/ | |