1

Ricostruzione di polyomini L-convessi

G. Castiglione, A. Restivo, R. Vaglica.

Dipartimento di Matematica e Applicazioni, Università di Palermo

2

due celle di un insieme discreto si dicono connesse se esiste un cammino (sequenza di celle adiacenti) che le collega contenuto nell’insieme.

Polyominoinsieme finito e connesso di celle (quadrati unitari) del piano cartesiano definito a meno di una traslazione

• Polyomino convesso

Polyomino convesso

: polyomino le cui righe e colonne sono connesse

3

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

In un polyomino convesso qualunque coppia di celle risulta connessa da almeno un cammino cammino monotonomonotono.

• Cammino monotono: cammino autoevitante costituito da passi in due sole direzioni

4

Proiezioni orizzontali e verticali(Tomografia discreta)

V 2 2 3 8 7 7 3 3

13388633H

Ricostruzione di insiemi discreti a partire da informazioni parziali

L-cammini

{ 1, 2, ... ,}

5

unicità

Ricostruzione banale (L-convessi)

Algoritmo di ricostruzione

Proiezioni orizzontali e verticali

(Tomografia discreta)

Ricostruzione di polyomini L-convessi

unicità

L-cammini

L-cammini bordati

L-camminimassimali

unicità

6

L(P) { x,y / x,y P }

Esempio

L-cammino 3,4 contenuto in un polyomino L-convesso

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

7

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)

(L(P), ) è un insieme parzialmente ordinato

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)

)}(,\max{)( max PLyxyPh

)}(,\max{)( max PLyxxPw

L-cammini massimali

8

Rettangoli massimali

Rmax(P): insieme di tutti gli elementi massimali di R(P)

[x,y] Polyomino di forma rettangolare avente larghezza x ed altezza y.

R(P) { [x,y] t.c. [x,y] P }parzialmente ordinato

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]}

x1 x2 … xn and y1 y2 … yn ordinamento canonico

9

rettangoli in posizione non

crossing

rettangoli in posizione crossing

Rettangoli non confrontabili in posizione 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.

Dati i rettangoli [x,y], [x',y'] non confrontabili si dice che essi si trovano in una posizione crossing se )],min(),,[min(],[],[ yyxxyxyx

10

se Rmax(P) {[x,y]}, ovvero P [x,y], e QL è tale che

Lmax(P) Lmax(Q) Q P

L famiglia dei polyomini L-convessi

• [x1 , y1] [w(P) , min{y : x,y Lmax(P),

xw(P) }]

• [xn , yn] [ min{x : x,y Lmax(P), yh(P) } ,

h(P) ]

Rmax(P) {[x1 , y1] , … , [xi , yi] , … , [xn , yn] }

ordine canonico

I polyomini L-convessi sono caratterizzati dai loro L-cammini massimali?

11

Lemma. Sia Rmax(P) 2. QL 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

Corrispondenza tra un polyomino L-convesso P e la famiglia Lmax(P )

12

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. 

P2P1

11,2

10,3

9,4

8,5

7,6

6,7

3,8

2,9

11, 2

10, 3

9, 4

7, 5

6, 6

4, 7

3, 8

2, 9

11,2

10,3

9,4

7,5

6,6

5,7

3,8

2,9

11, 2

10, 3

9, 4

6, 5

5, 6

4, 7

3, 8

2, 9

4 rettangoli massimali

2 occorrenze

13

Multiset ?

non è massimale

P1 P2

12,2 , 11,3 , 10,4 , 8,6 , 7,7 , 7,7 , 6,8 , ... , 2, 12

multiset

Questo esempio considera due polyomini L-convessi differenti aventi lo stesso multiset di L-cammini massimali.

14

2 88

6

3

3 7

3

86 3

1

(3,8),,(6,3),)8,2(SE

(3,7),,(6,1),)8,1(NE;

Polyomino L-convesso

L- cammini bordati

15

• Consistenza

• Ricostruzione

• Unicità

Problemi affrontati

16

L-cammini bordatiSia PP un polyomino convesso.

Un L-cammino è bordato in P P se

• 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

In particolare è detto :

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

##

#

#

#

#

##

##

17

Definizione di un L-cammino bordatoSia

Pjijijiπ mmss ),(,),,(,),,( 00

un L-cammino che cambia direzione nella cella . ),( ss ji

• EN bordato se è in direzione EN e

• NW bordato se è in direzione NW e

• WS bordato se è in direzione WS e

Pjijiji mmss )1,(),,1(),,1( 00

Pjijiji mmss ),1(),1,(),1,( 00

Pjijiji mmss )1,(),,1(),,1( 00

),( ji denota la cella

jjii ,1,1

Pjijiji mmss ),1(),1,(),1,( 00

π è detto

• SE bordato se è in direzione SE e

18

Definizione di una funzione di valutazione per un L-cammino

La size di un L-cammino

è la funzione

}0{\}0{\)(: NNPLs definita da

),(,),,(,),,( 00 mmss jijijiπ

),()( khπs dove

10 iih m 10 jjk m .

card (SE) = card (N W) = (P)

card (E N) = card (W S) = h(P)

tutte le coppie di interi positivi che rappresentano la size di un L-cammino SE bordato

SE =

Analogamente E N , W S, N W

19

Esempio

(3,7)(3,6),(6,3),(8,2),(8,1),(3,2),,(3,1),),11(NE

(3,1)(3,2),(6,1),(7,2),(8,3),(6,3),(7,2),,(8,2),),11(SE

##

#

##

#

##

#

# #

#

##

#

##

#

##

##

20

Struttura dell’algoritmo

Prima fase determina gli elementi di Rmax(P)

[x1,y1] [x2,y2]

[x3,y3] [x4,y4] x1 x2 x3 x4 and y1 y2 y3 y4

21

Seconda fase determina la mutua posizione dei rettangoli massimali a partire…Ω = (ω1, ω2, ω3, ω4)

Σ = (σ1, σ2, σ3, σ4)

ascisse dei SW corners

ordinate dei SW corners

1 11,1 ,

2 2, 3 3 4 4, ,

Struttura dell’algoritmo

22

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)

Dalla prova di questo lemma si ricava una procedura

per determinare gli elementi di Rmax(P) a partire

dall’insieme SE

ix

1ix

1 1i iy k

23

Seconda faseDue procedure che determinano Ω

ΩOMEGA1 (SE, E N)

OMEGA2 (SE, WS) Ω

Determinare la reciproca posizione di due rettangoli massimali

significa stabilire quale tipo di intersezione crossing hanno.

incrociato allineato a sinistra allineato a destra

1 ii j 1 ii 11 i iii xx

24

Seconda faseDue procedure che determinano Ω

ΩOMEGA1 (SE, E N)

OMEGA2 (SE, WS) Ω

• Scegliendo solo una delle due procedure …

… due tipi of sizes sono necessari!!!

(SE, WS) ΩOMEGA2

(SE, E N) (SE *, WS *) Ω* Σclock.rotation of π/2

OMEGA2

P P*2

25

ΩOMEGA1 (SE, E N)

OMEGA2 (SE, WS) Ω

Tuttavia il nostro scopo è ricostruire univocamente P da un’unica coppia di set di sizes.

Seconda fase

(SE, E N) ΩOMEGA1

(SE, E N) (SE *, WS *) Ω* Σclock.rotation of π/2

OMEGA2

Teorema: Ogni polyomino L-convesso è univocamente determinato da (SE, E N).