How to Catch $k$ Grid Points

Given a positive integer $k$, we study the problem of finding a convex polygon of minimum perimeter that encloses exactly $k$ points of ${\mathbf{Z}}^2$. We show that an optimal polygon is contained in a circular annulus of width $O(k^{1\mathrm{/}6})$, has $\mathrm{\Theta }(k^{1\mathrm{/}3})$ boundary grid points, and its longest edge has length $\mathrm{\Theta }(k^{1\mathrm{/}4})$. Using these structural bounds, we present a deterministic algorithm that computes an optimal polygon in $O(k^{29\mathrm{/}18+o(1)})$ time, improving over the previous $O(k^3)$-time algorithm.