Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
We show that packing axis-aligned unit squares into a simple polygon $P$ is NP-hard, even when $P$ is an orthogonal and orthogonally convex polygon with half-integer coordinates. It has been known since the early 80s that packing unit squares into a polygon with holes is NP-hard~[Fowler, Paterson, T...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2404.09835 http://arxiv.org/abs/2404.09835 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|