Drawing the Almost Convex Set in an Integer Grid of Minimum Size

In 2001, Károlyi, Pach and Tóth introduced a family of point sets to solve an Erdős–Szekeres type problem, which have been used to solve several other Erdős–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 equivalence of order type) nested almost convex set of n points, for any integer n. 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(nlog). Finally, we use our characterization to obtain an O(nlog⁡n)-time algorithm to determine whether a set of points is a nested almost convex set. © 2017 Elsevier B.V.