covering grid points in a convex polygon with straight lines^∗

^∗ This research work was partially supported by the National Science Council of the Republic of China under grant No. NSC80-0408-E009-03. To whom all the correspondence should be sent.

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.

Keywords:

• Approximation algorithm
• continued fraction expansionshitting set problem
• number theory

C.R. Categories:

• F.2.2
• G.2.1

^∗ This research work was partially supported by the National Science Council of the Republic of China under grant No. NSC80-0408-E009-03. To whom all the correspondence should be sent.

†To whom all the correspondence should be sent.

^∗ This research work was partially supported by the National Science Council of the Republic of China under grant No. NSC80-0408-E009-03. To whom all the correspondence should be sent.

†To whom all the correspondence should be sent.

Notes

^∗ This research work was partially supported by the National Science Council of the Republic of China under grant No. NSC80-0408-E009-03. To whom all the correspondence should be sent.

†To whom all the correspondence should be sent.