|
|||||
|
|
Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing |
|
| Authors: | Helmut Alt Esther M Arkin Alon Efrat George Hart Ferran Hurtado Irina Kostitsyna Alexander Kröller Joseph S B Mitchell Valentin Polishchuk |
| Affiliation: | 1. Institut für Informatik, Freie Universit?t, Berlin, Germany 2. Applied Mathematics and Statistics, Stony Brook University, Stony Brook, USA 3. Computer Science, The University of Arizona, Tucson, USA 4. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain 5. Computer Science, Stony Brook University, Stony Brook, USA 6. Computer Science, Technische Universit?t Braunschweig, Braunschweig, Germany 7. Helsinki Institute for IT, Computer Science, University of Helsinki, Helsinki, Finland |
| Abstract: | We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |