How to Catch $k$ Grid Points

Sariel Har-Peled, Elfarouk Harb, Qizheng He

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 poly…