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.
Optimizing rectangular partitions of histograms
Zoncape', Andrea
2010/2011
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
Andrea_Zoncapè_-_Optimizing_Rectangular_Partitions_of_Histograms.pdf
accesso aperto
Dimensione
1.72 MB
Formato
Adobe PDF
|
1.72 MB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/13396