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.
2010-04-19
54
partition, histogram, rectangular, thickest, optimize
File in questo prodotto:
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/13396