Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Zoncape', Andrea (2010) Optimizing rectangular partitions of histograms. [Laurea specialistica biennale]

Full text disponibile come:

[img]
Preview
PDF
1719Kb

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.

Item Type:Laurea specialistica biennale
Corsi di Laurea specialistica biennale:Facoltà di Ingegneria > Ingegneria informatica
Uncontrolled Keywords:partition, histogram, rectangular, thickest, optimize
Subjects:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Codice ID:23497
Relatore:Pucci, Geppino
Data della tesi:19 April 2010
Biblioteca:Polo di Ingegneria > Biblioteca di Ingegneria dell'Informazione e Ingegneria Elettrica "Giovanni Someda"
Tipo di fruizione per il documento:on-line per i full-text
Tesi sperimentale (Si) o compilativa (No)?:Yes

Solo per lo Staff dell Archivio: Modifica questo record