How to Catch k Grid Points

2026/07/12 by Sariel Har-Peled, Elfarouk Harb, Qizheng He · 1 voice
Computer Science · #cs.CG

paper · pdf

Abstract

Given a positive integer k, we study the problem of finding a convex polygon of minimum perimeter that encloses exactly k points of Z². 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³)-time algorithm.

Discussions

• arxiv.org/abs/2607.10824 [bsky, 0 points, 0 comments]

Related

• Finding Largest Rectangles in Convex Polygons
• A technique for solving the polygon inclusion problems
• Detecting all regular polygons in a point set
• Convex Polygon Containment: Improving Quadratic to Near Linear Time
• The Largest Contained Quadrilateral and the Smallest Enclosing Parallelogram of a Convex Polygon