Ricostruzione
di polyomini L-convessi
G. Castiglione, A. Restivo, R. Vaglica.
Dipartimento di Matematica e Applicazioni, Università di Palermo
1
Polyomino
insieme finito e connesso di celle (quadrati unitari)
del piano cartesiano definito a meno di una
traslazione
• Polyomino convesso : polyomino le cui righe e colonne
sono connesse
Polyomino convesso
 due celle di un insieme discreto si dicono connesse se esiste
un cammino (sequenza di celle adiacenti) che le collega
2
contenuto nell’insieme.
Polyomini L-convessi
polyomini convessi in cui ogni coppia di celle risulta connessa
da un cammino monotono con al più un solo cambiamento di
direzione (L-path)
L-convesso
L-convesso
• Cammino monotono: cammino autoevitante costituito
da passi in due sole direzioni
 In un polyomino convesso qualunque coppia di celle
3
risulta connessa da almeno un cammino monotono.
Ricostruzione di insiemi discreti a partire da
informazioni parziali
Proiezioni orizzontali e verticali
(Tomografia discreta)
V2 2 3 8 7 7 3 3
1
3
3
8
8
6
3
3

H
L-cammini
{ 1, 2, ... ,}
4
Ricostruzione di polyomini L-convessi
Proiezioni orizzontali e
verticali
(Tomografia discreta)
unicità
L-cammini
L-cammini
massimali
L-cammini
bordati
unicità
unicità
Ricostruzione banale
(L-convessi)
Algoritmo di ricostruzione
5
L-cammini
• L(P): insieme degli L-cammini contenuti nel polyomino
L-convesso P
Denotiamo con x,y (x,yℤ-{0}) un L-cammino fatto da |x|-1
passi orizzontali, |y|-1 passi verticali orientato come segue
•
se x>0 e y>0
•
se x>0 e y<0
•
se x<0 e y>0
•
se x<0 e y<0
L(P) { x,y / x,y  P }
Esempio
L-cammino 3,4
contenuto in un
polyomino L-convesso
6
L-cammini massimali
(L(P), ) è un insieme parzialmente ordinato
• x,y è massimale (in L(P)) se
 x',y'  L(P) , x,y  x',y'  x  x'  y  y'
Lmax(P): insieme di tutti gli elementi massimali di L(P)
Osservazione: gli elementi di Lmax(P) possono avere più occorrenze
in P. Tutte queste occorrenze connettono celle appartenenti ai bordi
di P
Relazione tra altezza e larghezza di
P e l’insieme Lmax(P)
h( P)  max{ y \ x, y   Lmax ( P)}
w( P)  max{ x \ x, y   Lmax ( P)}
7
Rettangoli massimali
[x,y]  Polyomino di forma rettangolare avente larghezza x ed
altezza y.
parzialmente ordinato
R(P) { [x,y] t.c. [x,y]  P }
Rmax(P): insieme di tutti gli elementi massimali di R(P)
Osservazione: Rmax(P) è un insieme finito di rettangoli non
confrontabili ovvero  [x,y], [x',y']Rmax(P) tali
che
[x,y]  [x',y']  [x',y']  [x,y]
Rmax(P) {[x1,y1] , [x2,y2] , … , [xn,yn]}
ordinamento canonico
x1  x2  …  xn and y1  y2  …  yn
8
Rettangoli non confrontabili in posizione crossing
Dati i rettangoli [x,y], [x',y'] non confrontabili si dice che essi si trovano
in una posizione crossing se [ x, y ]  [ x, y]  [min( x, x), min( y, y)]
rettangoli in posizione crossing
rettangoli in posizione
non crossing
Teorema: Un polyomino convesso P è un L-convesso se e solo se i suoi
rettangoli massimali hanno a due a due una posizione crossing in P. 9
I polyomini L-convessi sono caratterizzati
dai loro L-cammini massimali?
Rmax(P) {[x1 , y1] , … , [xi , yi] , … , [xn , yn] }
• [x1 , y1]  [w(P) , min{y : x,y Lmax(P), xw(P) }]
• [xn , yn]  [ min{x : x,y Lmax(P), yh(P) } , h(P) ]
ordine canonico
se Rmax(P)  {[x,y]}, ovvero P  [x,y], e QL è tale che
Lmax(P)  Lmax(Q)  Q  P
L  famiglia dei polyomini L-convessi
10
Corrispondenza tra un polyomino
L-convesso P e la famiglia Lmax(P )
Lemma. Sia Rmax(P)  2.  QL tale che Lmax(P)  Lmax(Q), la dimensione e
la reciproca posizione del primo e secondo (penultimo ed ultimo) rettangolo
massimale di Q coincideranno con quelle del primo e del secondo (penultimo ed
ultimo rispettivamente) rettangolo massimale di P.
Teorema. Sia P L. Se Rmax(P)  3 allora P è univocamente determinato da
Lmax(P) .
Lmax(P)  P
nel caso in cui P è costituito
al più da 3 rettangoli
massimali
11
Controesempio
Questo esempio considera due polyomini L-convessi
distinti, con più di tre rettangoli massimali, aventi lo
stesso insieme di L-cammini massimali riportato in
tabella.
11, 2
11,2
11, 2
11,2
10,3
10, 3
10,3 10, 3
9,4
9, 4
9,4
9, 4
8,5
7, 5
7,5
6, 5
7,6
6, 6
6,6
5, 6
6,7
4, 7
5,7
4, 7
3,8
3, 8
3,8
3, 8
2,9
2, 9
2,9
2, 9
4 rettangoli massimali
P1
P2
2 occorrenze
12
Multiset ?
Questo esempio considera due polyomini L-convessi differenti aventi lo stesso
multiset di L-cammini massimali.
P1
P2
non è massimale
multiset
 12, 2 , 11,3 , 10, 4 , 8, 6 , 7, 7  , 7, 7  , 6,8 , ... ,  2, 12
13
L- cammini bordati
2
3
8
8
8
6
3
6
7
3
3
SE   (8,2) , (6,3) , (3,8), 

1




E
N

 (8,1) , (6,1) , (3,7), 
;




Polyomino L-convesso
14
Problemi affrontati
• Consistenza
• Ricostruzione
• Unicità
15
L-cammini bordati
Sia P un polyomino convesso.
Un L-cammino  è bordato in P se
 parte da una cella del bordo
 procede ortogonalmente rispetto allo stesso bordo
 quando incontra il bordo opposto gira in senso antiorario
#
 quindi procede dritto fino al bordo opposto
In particolare  è detto :
• SE bordato se parte dal bordo superione
• EN bordato se parte dal bordo sinistro
• NW bordato se parte dal bordo inferiore
• WS bordato se parte dal bordo destro

#
#
# #

#
#
# #

 
# 16
Definizione di un L-cammino bordato
Sia
π  (i0 , j0 ),  , (is , j s ),  , (im , jm )  P
un L-cammino che cambia direzione nella cella (is , js ) .
π è detto
• SE bordato se è in direzione SE e (i0 , j0  1), (is , js  1), (im  1, jm )  P
• EN bordato se è in direzione EN e (i0  1, j0 ), (is  1, js ), (im , jm  1)  P
• NW bordato se è in direzione NW e (i0 , j0  1), (is , js  1), (im  1, jm )  P
• WS bordato se è in direzione WS e (i0  1, j0 ), (is  1, js ), (im , jm  1)  P
 (i, j ) denota la cella
i  1, i   j  1, j 
17
Definizione di una funzione di valutazione
per un L-cammino
La size di un L-cammino
è la funzione
π  (i0 , j0 ),  , (is , js ),  , (im , jm )
s : L( P)  N \ {0}  N \ {0}
definita da
dove
SE =
s (π )  (h, k )
h  im  i0  1
k  j m  j0  1 .
tutte le coppie di interi positivi che rappresentano
la size di un L-cammino SE bordato
Analogamente E N , W S, N W
 card (SE) = card (N W) = (P)
 card (E N) = card (W S) = h(P)
18
Esempio
SE   (1,1) , (8,2), (7,2),(6,3),(8,3),(7,2),(6,1), (3,2), (3,1)

 
  
##



 
#
###
##
#
#
#





#



##
#
##
#
#
#
#
#
E N   (1,1) , (3,1), (3,2),(8,1),(8,2),(6,3),(3,6), (3,7)
19



Struttura dell’algoritmo
Prima fase  determina gli elementi di Rmax(P)
[x1,y1]
[x2,y2]
x1  x2  x3  x4 and y1  y2  y3  y4
[x3,y3]
[x4,y4]
20
Struttura dell’algoritmo
1,1  1,1 
2 , 2 
3 , 3   4 , 4 
Seconda fase  determina la mutua posizione dei
rettangoli massimali a partire…
Ω = (ω1, ω2, ω3, ω4)
 ascisse dei SW corners
Σ = (σ1, σ2, σ3, σ4)
 ordinate dei SW corners
21
Prima fase
LEMMA. Sia P un polyomino L-convesso. Gli elementi di
Rmax(P) sono univocamente determinati da SE
(o equivalentemente da E N , N W , W S)
yi 1  ki 1
xi
xi 1
 Dalla prova di questo lemma si ricava una procedura per
determinare gli elementi di Rmax(P) a partire dall’insieme SE
22
Seconda fase
Due procedure che determinano Ω
OMEGA1 (SE, E
N) 
Ω
Ω
OMEGA2 (SE, WS)

incrociato
allineato a sinistra
i 1  i  j
i 1  i
allineato a destra
i 1  i  xi  xi 1
 Determinare la reciproca posizione di due rettangoli massimali
significa stabilire quale tipo di intersezione crossing hanno.
23
Seconda fase
Due procedure che determinano Ω
OMEGA1 (SE, E
N) 
OMEGA2 (SE, WS)

Ω
Ω
• Scegliendo solo una delle due procedure …
(SE, WS)
(SE, E N)
clock.rotation of π/2
OMEGA2
(SE *, WS *)
… due tipi of sizes sono necessari!!!
Ω
OMEGA2
P
Ω*

2
P*
Σ
24
Seconda fase
OMEGA1 (SE, E
N) 
OMEGA2 (SE, WS)

Ω
Ω
 Tuttavia il nostro scopo è ricostruire univocamente P da un’unica
coppia di set di sizes.
(SE, E N)
(SE, E N)
clock.rotation of π/2
OMEGA1
(SE *, WS *)
Ω
OMEGA2
Ω*
Σ
Teorema: Ogni polyomino L-convesso è univocamente determinato da (SE, E N).
25