Polyomini L-convessi
A.Restivo e G.Castiglione (Unità di Palermo)
A. Frosini e S. Rinaldi (Unità di Firenze-Siena)
Ravello 19-21 settembre 2003
Problemi
• Definizione e caratterizzazione dei polyomini L-convessi;
• Algoritmo di ricostruzione di un polyomino L-convesso
dalla famiglia delle L massimali;
• Ricostruzione unica di un polyomino L-convesso dalle
sue proiezioni ortogonali;
• Enumerazione dei polyomini L-convessi rispetto al
semiperimetro;
Ravello 19-21 settembre 2003
Polyomini convessi
Polyomini:insieme finito e connesso di celle adiacenti.
Polyomino convesso: righe e collonne connesse.
Ravello 19-21 settembre 2003
Polyomini L-convessi
Polyomini convessi in cui per ogni coppia di celle esiste
un cammino monotono, con al piu’ un cambiamento di
direzione, che le collega.
P e’ L-convesso  i suoi rettangoli massimali hanno a
due a due una posizione crossing
Unione finita di rettangoli non confrontabili, in posizioni
crossing.
Ravello 19-21 settembre 2003
Proiezioni ortogonali (H,V)
1
1
0
0
0
1
1
1
1
1
1
1
1
1
0
0
2 3 4 2
3
4
2
2
M=(aij)
H=(h1,h2,…,hn)Nn
V=(v1,v2,…,vm) Nm
m
 aij  hi
j1
n
 aij  v j
M(H,V)
i=1,2,…,n
j=1,2,…,m
i1
la classe delle matrici binarie con proiezioni
ortogonali (H,V).
Ravello 19-21 settembre 2003
Problemi
• Consistenza
• Ricostruzione
• Unicità
Una matrice binaria M si dice unica rispetto alle sue
proiezioni ortogonali (H,V) se non esiste un’altra
matrice binaria BA in M(H,V).
Ravello 19-21 settembre 2003
Cns per l’unicità
Teorema: Una matrice binaria è non unica (rispetto alle sue
proiezioni ortogonali) se e solo se ha componenti di switch.
1 0 1 1
0 1 1 1
0 1 0 1
0 1 1 0
1 3 3 3
3
3
2
2
0 1 1 1
switching
1 0 1 1
0 1 0 1
0 1 1 0
3
3
2
2
1 3 3 3
Ravello 19-21 settembre 2003
Cns per l’unicità
Siano HN n e VNm due vettori unimodali,
M(H,V)={M} se e solo se M è un polyomino L-convesso
0
0
1
0
0
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
0
0
0
1
1
0
1
4
5
4
3
A=(a1,a2,…,an)Nn è unimodale
se esiste 1kn tale che
a1... a1 e ak+1... an
1 4 5 4 3 2
Ravello 19-21 settembre 2003
Cns per l’unicità
Siano HNn e VNm due vettori unimodali,
M(H,V)={M} se e solo se M è un polyomino L-convesso
0
0
1
0
0
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
0
0
0
1
1
0
Ravello 19-21 settembre 2003
Enumerazione degli L-convessi
L, Ln
:
Ln P(Ln+1)
Proposizione: Se  è un operatore tale che:
• per ogni L’Ln+1 esiste L Ln tale che L’ (L)
• presi L,L’  Ln con LL’ si ha che  (L)   (L’)= 
allora la famiglia degli insiemi
partizione di
Ln+1.
Fn+1={ (L): L  Ln} è una
Ravello 19-21 settembre 2003
Definizione dell’operatore 

Classe A: >1
Applicando  ad un polyomino di semiperimetro n della classe
A si ottengono 2+1 polyomini di semiperimetro n+1
Ravello 19-21 settembre 2003
Definizione dell’operatore 
Classe B: =1
Una sola cella
nell’ultima colonna
Applicando  ad un polyomino di semiperimetro n della classe
B si ottengono 2 polyomini di semiperimetro n+1
Ravello 19-21 settembre 2003
Definizione dell’operatore 
Classe C: =1
Più di una cella
nell’ultima colonna
Applicando  ad un polyomino di semiperimetro n della classe
C si ottengono 3 polyomini di semiperimetro n+1
Ravello 19-21 settembre 2003
Albero di generazione
(2)
(2)
(2) (5)
(5)
(2) (2) (3) (3) (5)
Con l’etichetta (k) denotiamo i polyomini che attraverso 
producono k polyomini, quindi
(2) i polyomini della classe A;
(3) i polyomini della classe B;
(2+1), >1 i polyomini della classe C.
Ravello 19-21 settembre 2003
Albero di generazione e regole di
produzione
(2)
(2)
(2) (5)

(5)
(2) (2) (3) (3) (7)
(2)
(2)(2)(5)
(2+1)(2)(3)(2+3)
Ravello 19-21 settembre 2003
Funzione generatrice
Denotiamo con:
• L l’insieme delle etichette nell’albero di generazione.
L(s , x , y , q) 
l(P) h(P) w (P) a(P)
s
 x y q
PL
• D l’insieme delle etichette (2) nell’albero;
• E l’insieme delle etichette (2+1), 1.
L(s,x,y,q)=D(s,x,y,q)+E(s,x,y,q)
L(x )  L(1, x , x ,1) 
(1  x )2
1  4 x  2 x2
Ravello 19-21 settembre 2003
Relazione di ricorrenza
L(x )  L(1, x , x ,1) 

Ln 
(1  x )2
1  4 x  2 x2
L0=1 L1=2 L2=7
Ln=4Ln-1-2Ln-2
n3
1 2
1 2
(2  2 )n 
(2  2 )n
4
4
Ravello 19-21 settembre 2003
Lavori in corso
•
Enumerazione secondo l’area dei polyomini L-convessi;
• L-convessi nello spazio a tre dimensioni;
• L-convessi nel continuo.
FINE
Ravello 19-21 settembre 2003