Drawing the almost convex set in an integer grid of minimum size

In 2001, Karolyi, Pach and Toth introduced a family of point sets to solve an Erdos-Szekeres type problem; which have been used to solve several other Edos-Szekeres type problems. In this paper we refer to these sets as nested almost convex sets. A nested almost convex set X has the property that the interior of every triangle determined by three points in the same convex layer of X , contains exactly one point of X . In this paper, we introduce a characterization of nested almost convex sets. Our characterization implies that there exists at most one (up to order type) nested almost convex set of n points. We use our characterization to obtain a linear time algorithm to construct nested almost convex sets of n points, with integer coordinates of absolute values at most O(n log 25). Finally, we use our characterization to obtain an O (n logn)-time algorithm to determine whether a set of points is a nested almost convex set.

• Autores: Duque Patiño, Frank Rodrigo; Fabila Monroy, Ruy; Hidalgo Toscano, Carlos; Pérez Lantero, Pablo
• 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/46313
• Acceso en línea: https://hdl.handle.net/10495/46313
• Palabra clave: Conjuntos convexos; Convex sets; Coordenadas cartesianas; Teoría de conjuntos; Set theory; Grupos de puntos; Groups of points
• Rights: openAccess
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/