Optimizing rectangular partitions of histograms
Andrea Zoncape · 2010
The problem of partitioning isothetic polygons into rectangles, where the goal is to minimise the total length of the partition, has some applications in VLSIcircuit design and construction. If these polygons have holes inside, the problem becomes NP-hard, instead, in the case of hole-free polygons, an optimal partition can be computed in O(n4) exploiting dynamic programming. In this thesis, I focus my attention on rectangular partitions of histograms, which are special cases of hole-free isothetic polygons, using the fact it's possible to partition them into histograms in linear time. I've used dynamic programming in order to produce optimal partitions and a parameterised approximation algorithm, a variant of the so called thickest first algorithm. Then, I've compared experimentally these two algorithms to check theoretical bounds and to evaluate the goodness of the approximation algorithm, especially on some interesting histogram shapes like staircase and staircase united with its mirror image. In parallel, an interactive tool has been implemented, with a graphical representation, which can help users to visualise the differences between these methods. The implementation of the algorithms, the auxiliary structures and the GUI of the tool have been implemented with C++ and Qt graphics libraries.