Ordered Strip Packing

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


We study an ordered variant of the well-known strip packing problem, which is motivated by applications in visualization and typography. Our input consists of a maximum width W and an ordered list of n blocks (rectangles). The goal is to pack the blocks into rows (not exceeding W) while obeying the given order and minimizing either the number of rows or the total height of the drawing. We consider two variants: (1) non-overlapping row drawing (NORD), where distinct rows cannot share y-coordinates, and (2) overlapping row drawing (ORD), where consecutive rows may overlap vertically. We present an algorithm that computes the minimum-height NORD in O(n) time. Further, we study the worst-case tradeoffs between the two optimization criteria—number of rows and total height—for both NORD and ORD. Surprisingly, we show that the minimum-height ORD may require Ω(log n/ log log n) times as many rows as the minimum-row ORD. The proof of the matching upper bound employs a novel application of information entropy.

Originele taal-2Engels
TitelLATIN 2020
SubtitelTheoretical Informatics - 14th Latin American Symposium 2021, Proceedings
RedacteurenYoshiharu Kohayakawa, Flávio Keidi Miyazawa
UitgeverijSpringer Science and Business Media Deutschland GmbH
Aantal pagina's13
ISBN van geprinte versie9783030617912
StatusGepubliceerd - 2020
Evenement14th Latin American Symposium on Theoretical Informatics, LATIN 2020 - Sao Paulo, Brazilië
Duur: 5 jan 20218 jan 2021

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12118 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres14th Latin American Symposium on Theoretical Informatics, LATIN 2020
StadSao Paulo

Vingerafdruk Duik in de onderzoeksthema's van 'Ordered Strip Packing'. Samen vormen ze een unieke vingerafdruk.

Citeer dit