COVERING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES

Abstract

We consider the following problem: Find a set of parallel straight lines with equal spacing to hit all m grid points in a closed region bounded by a convex polygon P with n vertices such that size of this set is minimal. We use continued fraction expansions to explore the combinatorial properties of this problem and propose an O(n + log m) approximation algorithm which guarantees finite performance ratio.