Drawing the Horton set in an integer grid of minimum size

In 1978 Erdos asked if every sufficiently large set of points in general position in the plane contains the vertices of a convex k-gon, with the additional property that no other point of the set lies in its interior. Shortly after, Horton provided a construction—which is now called the Horton set—with no such 7-gon. In this paper we show that the Horton set of n points can be realized with integer coordinates of absolute value at most 12n 12 log(n/2). We also show that any set of points with integer coordinates combinatorially equivalent (with the same order type) to the Horton set, contains a point with a coordinate of absolute value at least c · n 1/24 log(n/2) , where c is a positive constant.

• Autores: Duque Patiño, Frank Rodrigo; Barba Flores, Luis; Fabila Monroy, Ruy; Hidalgo Toscano, Carlos
• Tipo de recurso: Article of investigation
• Fecha de publicación: 2017
• Institución: Universidad de Antioquia
• Repositorio: Repositorio UdeA
• Idioma: eng
• OAI Identifier: oai:bibliotecadigital.udea.edu.co:10495/46334
• Acceso en línea: https://hdl.handle.net/10495/46334
• Palabra clave: Grupos de puntos; Groups of points; Conjuntos convexos; Convex sets; Geometría combinatoria; Combinatorial geometry; Convex holes; Convex holes; Horton sets; Agujeros convexos
• Rights: openAccess
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/