Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Scandinavian thins on top of cake: new and improved algorithms for stacking and packing

Autor
Alt, H.; Arkin, E. M.; Efrat, A.; Hart, G.; Hurtado, F.; Kostitsyna, I.; Kröller, A.; Mitchell, J. S. B.; Polishchuk, V.
Tipus d'activitat
Article en revista
Revista
Theory of computing systems
Data de publicació
2014-05-01
Volum
54
Número
4
Pàgina inicial
689
Pàgina final
714
DOI
https://doi.org/10.1007/s00224-013-9493-9 Obrir en finestra nova
Projecte finançador
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
URL
http://link.springer.com/article/10.1007%2Fs00224-013-9493-9 Obrir en finestra nova
Resum
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 sim...
Paraules clau
Computational Geometry, Enclosure, Packing, Polygon Containment, Maximum Overlap, Area, Constructions, Translations, Rectangles, Polytopes, Circles, Points, Square
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Alt, Helmut  (autor)
  • Arkin, Esther M.  (autor)
  • Efrat, Alon  (autor)
  • Hart, George W.  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Kostitsyna, Irina  (autor)
  • Kröller, Alexander  (autor)
  • Mitchell, Joseph S. B.  (autor)
  • Polishchuk, Valentin  (autor)