Optimally Decomposing Coverings with Translates of a Convex Polygon |
| |
| Authors: | Matt Gibson Kasturi Varadarajan |
| |
| Institution: | (1) Institute of Applied Mathematics, Chinese Academy of Science, Beijing, China;(2) Department of Computer Science, Memorial University of Newfoundland, St. John s, Newfoundland, A1B 3X5, Canada |
| |
| Abstract: | We show that any k-fold covering using translates of an arbitrary convex polygon can be decomposed into Ω(k) covers. Such a decomposition can be computed using an efficient (polynomial-time) algorithm. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
