| Автор | Lee, H.S. |
| Автор | Chang, R.C. |
| Дата выпуска | 1992 |
| dc.description | 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. |
| Формат | application.pdf |
| Издатель | Gordon and Breach Science Publishers |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | Approximation algorithm |
| Тема | continued fraction expansionshitting set problem |
| Тема | number theory |
| Тема | F.2.2 |
| Тема | G.2.1 |
| Название | covering grid points in a convex polygon with straight lines |
| Тип | research-article |
| DOI | 10.1080/00207169208804057 |
| Electronic ISSN | 1029-0265 |
| Print ISSN | 0020-7160 |
| Журнал | International Journal of Computer Mathematics |
| Том | 42 |
| Первая страница | 137 |
| Последняя страница | 156 |
| Аффилиация | 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 |
| Выпуск | 3-4 |
| Библиографическая ссылка | Garey, M.R. and Johnson, D.S. 1979. “Computers and Intractability”. In A Guide to the Theory of NP- Completeness, San Francisco, California: Fremman. |
| Библиографическая ссылка | Greene, D.H. and Yao, F.F. Finite-resolution computational geometry. Proc. 27th Symposium on Foundations of Computer Science. pp.143–152. |
| Библиографическая ссылка | Hassin, R. and Megiddo, N. 1991. Approximation algorithms for hitting objects with straight lines. Discrete Applied Mathematics, 30(1): 29–24. |
| Библиографическая ссылка | Knuth, D.E. 1981. The Art of Computer Programming, Addison-Wesley. second edition |
| Библиографическая ссылка | Lee, H.S. and Chang, R.C. 1991. Weber problem on a grid Techn. Rep., Dept. of Comp. Science and Info. Engineering, NCTU |
| Библиографическая ссылка | LeVeque, W.J. 1977. Fundamentals of Number Theory, Addison-Wesley. |
| Библиографическая ссылка | Lovasz, L. 1986. “Society for Industrial and Applied Mathematics”. In An Algorithmic Theory of Numbers, Graphs and Complexity Pennsylvania |
| Библиографическая ссылка | Mehta, S., Mukherjeel, M. and Nagy, G. Constrained integer approximation to 2-D line intersections. Second Canadian Conf on Computational Geometry. August. pp.302–305. Canada |
| Библиографическая ссылка | Overmars, M.H. 1988. “Computational geometry on a grid: an overview”. In Theoretical Foundations for Computer Graphics and CAD, 167–184. Berlin: Springer-Verlag. |
| Библиографическая ссылка | Preparata, F.P. and Shamos, M.I. 1985. Computational Geometry:An Introduction, New York: Springer-Verlag. |
