Drawing the almost convex set in an integer grid of minimum size (2017)
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.