Partitioning Orthogonal Histograms Into Rectangular Boxes
Published in LATIN, 2018
Recommended citation: Therese Biedl, Martin Derka, Veronika Irvine, Anna Lubiw, Debajyoti Mondal, and Alexi Turcotte. 2018. Partitioning Orthogonal Histograms Into Rectangular Boxes. Latin American Theoretical Informatics Symposium, LATIN, 14 pages. http://reallytg.github.io/files/papers/latin18-histograms.pdf
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.