Problemi di Set Covering e applicazioni alla stampa 3D

In questa tesi presentiamo uno studio di problemi di ricoprimento di insieme mediante algoritmi di Set Covering applicati al campo della stampa 3D di muri. Lo scopo è definire un ricoprimento del muro che minimizzi il numero di stampanti utilizzate per la stampa, il rischio di collisioni fra le stampanti, e renda uniforme le aree stampate da ciascuna stampante. Introduciamo dapprima la teoria del Set Covering, e i problemi di impacchettamenti, ricoprimenti e piastrellamenti nel caso bidimensionale. Analizziamo poi gli impacchettamenti e ricoprimenti congruenti e finiti, e in particolare i ricoprimenti finiti mediante cerchi congruenti di domini quadrati e rettangolari. Presentiamo gli algoritmi di Set Covering e i metodi computazionali che implementano la teoria, focalizzandoci principalmente sugli algoritmi greedy con costi unitari e sui metodi di minimo. Infine applichiamo risolviamo in modo ottimale al nostro problema di stampa 3D proponendo un algoritmo che combina algoritmi greedy e metodi di minimo come la Steepest Descent. Questo studio è stato svolto in collaborazione con l’azienda WASP S.R.L..