How to Catch $k$ Grid Points
2026-07-12 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study how to find the smallest perimeter convex polygon that exactly encloses a given number k of points on a grid. They discover that such a polygon fits within a thin ring-shaped area and has about k^(1/3) points on its boundary, with edges of length around k^(1/4). Using these insights, the authors develop a faster algorithm to find this polygon, which runs in roughly O(k^(1.61)) time, improving on the previous slower O(k^3) method.
convex polygonperimeter minimizationinteger latticealgorithm complexitycircular annulusboundary pointsedge lengthcomputational geometrydeterministic algorithm
Authors
Sariel Har-Peled, Elfarouk Harb, Qizheng He
Abstract
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/6})$, has $Θ(k^{1/3})$ boundary grid points, and its longest edge has length $Θ(k^{1/4})$. Using these structural bounds, we present a deterministic algorithm that computes an optimal polygon in $O(k^{29/18+o(1)})$ time, improving over the previous $O(k^3)$-time algorithm.