EUVIMEDEUVIMED entdecken
Crossref

Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares

Mikkel Abrahamsen, Jack Stade

SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-29-FOCS24-84

DOI: 10.1137/24m171824x ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 25.11.2025. Verfasst von Mikkel Abrahamsen und 1 weiteren Autor:innen. Die Arbeit nennt 53 Literaturangaben. Gefördert von: Independent Research Fund Denmark, Carlsberg Foundation, Villum Fonden.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

It has been known since the early 1980s that packing unit squares into a polygon with holes is NP-hard [Fowler, Paterson, Tanimoto, Inf. Process. Lett., 1981], but the version without holes was conjectured to be polynomial-time solvable more than two decades ago [Baur and Fekete, Algorithmica, 2001]. We show that packing axis-aligned unit squares into a simple polygon [Formula: see text] is NP-hard even when [Formula: see text] is an orthogonal and orthogonally convex polygon with half-integer coordinates. Our results can be extended to show hardness of covering simple polygons with unit squares and partitioning simple polygons into pieces that fit inside a unit square.

Förderung

  • Independent Research Fund Denmark
  • Carlsberg Foundation
  • Villum Fonden

Zitieren

APA

Abrahamsen, M., & Stade, J. (2026). Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares. SIAM Journal on Computing, 55(5), FOCS24-29-FOCS24-84. https://doi.org/10.1137/24m171824x

Vancouver

Abrahamsen M, Stade J. Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares. SIAM Journal on Computing. 2026;55(5):FOCS24-29-FOCS24-84. doi:10.1137/24m171824x

BibTeX
@article{Abrahamsen2026,
  author = {Abrahamsen, Mikkel and Stade, Jack},
  title = {Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {5},
  pages = {FOCS24--29--FOCS24--84},
  doi = {10.1137/24m171824x}
}
Kostenlos starten →