covering grid points in a convex polygon with straight lines
Lee, H.S.; Chang, R.C.; Lee, H.S.; Institute of Computer Science and Information Engineering, National Chiao Tung University; Chang, R.C.; Institute of Computer and Information Science, National Chiao Tung University
Журнал:
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.
556.0Кб