Tomografia discreta

Programma: Algoritmi per la ricostruzione di poliomini convessi a partire dalle loro proiezioni orizzontali e verticali.
Martedì 7 Ottobre, ore 11.00 - aula seminari 3o piano.

Sunto. Verranno presentati due algoritmi polinomiali per la ricostruzione di poliomini convessi (cioé poliomini le cui righe e colonne sono connesse). Il primo algoritmo è basato su alcune semplici operazioni che vengono applicate a righe e colonne e sull’eventuale riduzione al problema della 2-soddisfacibilità e si dimostra che se esiste un poliomino che soddisfa le proiezioni date questo viene sempre individuato. L’altro algoritmo utilizza ancora le stesse operazioni su righe e colonne ma in più si avvale di alcune proprietà sulle mediane di insiemi discreti. Questo consente di ridurre la complessità, ma non è dimostrato che l’algoritmo individui sempre la soluzione, anche se questo si è verificato sempre nelle prove eseguite.

Problemi di ambiguit`a nella ricostruzione di insiemi discreti a partire dalle loro proiezioni.
Martedì 7 ottobre, ore 15.00 - aula seminari 3o piano.

Sunto. Verrà esaminato il problema dell’unicità della soluzione per la ricostruzione di insiemi discreti a partire dalle loro proiezioni. Verranno considerate diverse classi di insiemi discreti ottenute imponendo alcune proprietà quali connessione, convessità, ... inviduando le proprietà e gli insiemi di proiezioni che garantiscono l’unicità della soluzione. Verrà inoltre presentata una congettura secondo la quale 4 proiezioni, scelte opportunamente, sono sufficienti per avere l’unicità dei poliomini convessi, mostrando anche un programma che è stato utilizzato per ottenere una verifica sperimentale della congettura.

Ricostruzione di insiemi discreti per mezzo di proiezioni con assorbimento.
Mercoledì 8 ottobre, ore 11.00 - aula seminari 3o piano.

Sunto. In alcuni recenti lavori, A. Kuba e M. Nivat hanno introdotto un modello di proiezioni con assorbimento. In questo caso le proiezioni lungo una direzione non sono più date dal numero di punti che si trovano sulle rette parallele alla direzione stessa ma da somme pesate mediante dei coefficienti. Nel caso che questi soddisfino una ricorrenza analoga a quella dei numeri di Fibonacci, gli autori mostrano che le proiezioni orizzontali e verticali non sono sufficienti a garantire l’unicità della soluzione. Verrà invece mostrato che le sole proiezioni orizzontali, considerate però nei due versi, sono sufficienti per garantire l’unicità e permettono anche di definire un algoritmo di ricostruzione lineare.