Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Partitioning Orthogonal Histograms into Rectangular Boxes
verfasst von : Therese Biedl, Martin Derka, Veronika Irvine, Anna Lubiw, Debajyoti Mondal, Alexi Turcotte
Erschienen in: LATIN 2018: Theoretical Informatics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The problem of partitioning an orthogonal polyhedron into a minimum number of boxes was shown to be NP-hard in 1991, but no approximability result is known except for a 4-approximation algorithm for 3D-histograms. In this paper we broaden the understanding of the 3D-histogram partitioning problem. We prove that partitioning a 3D-histogram into a minimum number of boxes is NP-hard, even for histograms of height two. This settles an open question posed by Floderus et al. We then show the problem to be APX-hard for histograms of height four. On the positive side, we give polynomial-time algorithms to compute optimal or approximate box partitions for some restricted but interesting classes of polyhedra and 3D-histograms.