covering grid points in a convex polygon with straight lines∗
Heesang Lee, R.C. Chang · International Journal of Computer Mathematics · 1992
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.