Sono un marito fedele.
Ma ci sono degli amori passati che ogni tanto tornano a stimolarmi e a riempirmi
la mente, facendomi rivivere le emozioni che provavo quando li frequentavo. E allora
eccomi lì a centellinarne i piaceri che ancora una volta, con rinnovato vigore,
mi si concedono, quasi nell'ingenuità di una cotta adolescenziale.
Uno di questi amori è la Matematica.
;-)
È grazie a Giovanna e al suo blog
Matematicamedie che mi sono imbattuto in un aspetto
di questa materia a me ancora sconosciuto. Non avevo mai sentito parlare prima,
infatti, del teorema di Pick.
Come la prof. Giovanna spiega esaurientemente nel suo
interessantissimo post, che
parla di un magnifico lavoro in cui ha guidato la classe dei suoi allievi, il teorema
di Pick calcola in modo semplice e conciso l'area di un poligono costruito in un
modo particolare.
Per chiarire meglio la faccenda, comincio con qualche definizione.
Avendo una griglia regolare di punti (che possiamo immaginare come gli incroci delle
linee di un foglio quadrettato), un "segmento di Pick" è un segmento che unisce
due punti della griglia senza incontrarne alcun altro nel suo cammino. Se il segmento
incontra qualche altro punto, viene considerato piuttosto come il concatenamento
di due segmenti consecutivi allineati.
Un "poligono di Pick" è un concatenamento chiuso e non autointersecante di segmenti
di Pick.
È proprio l'area del poligono di Pick che è valutata dal teorema di Pick.
Si noti che la condizione di non-autointersezione è necessaria per il calcolo dell'area.

figura 1
Non avrebbe infatti molto senso valutare l'area di un poligono autointersecante.
Inoltre la condizione per cui un segmento non deve contenere nessun punto della
griglia oltre gli estremi, non riduce l'espressività della definizione. Se un
poligono ha un lato tagliato da un punto della griglia, be', in quel punto si può
considerare un vertice aggiuntivo che forma un angolo piatto. Ad esempio la figura
1 mostra un poligono di Pick costituito da quattro vertici e quattro lati,
indicati da colori diversi, pur essendo perfettamente sovrapponibile ad un triangolo.
Come rivela Giovanna, il teorema di Pick afferma che l'area
A di un poligono
di Pick è data dalla formula
A = PI + PC/2
-1
dove
PI è il numero di punti "interni"
al poligono (cioè i punti della griglia regolare che cadono nella parte interna)
e
PC è il numero di punti "al contorno",
cioè quelli che costituiscono i vertici dei segmenti di Pick lati del poligono,
o, in altre parole, i punti che giacciono sul perimetro.
Evidentemente la formula è valida a meno di moltiplicare il valore ottenuto per
l'area del quadretto che definisce la griglia regolare. Per semplicità su questo
post si supporrà di considerare una griglia il cui quadretto ha area unitaria.
Riprendendo la figura 1, ad esempio,
PI
è il numero di punti colorati in azzurro (
7),
PC quelli in giallo (
4), quindi l'area
del poligono è
A = 7 + 4/2 - 1 = 8
Funziona. Provare per credere!
In un commento della discussione di seguito al blog citato, Giovanna mi suggerisce
un paio di link dove c'è pure la dimostrazione "ufficiale" del teorema di Pick.
Io però non ho ancora seguito quei link, ne' ho intenzione di farlo prima di aver
inserito questo post, perché ciò che mi affascina della matematica non è tanto
il risultato in sè, anche se in casi come questo la formula ha un'eleganza davvero
attraente. Ne' tanto meno ho bisogno di una prova concreta per credere nella verità
della formula: mi fido di Giovanna!
No, l'aspetto che trovo irresistibile è utilizzare la matematica per trovare una
dimostrazione da me.
Questo compito è naturalmente semplificato dal fatto che so già in anticipo quale
sia il risultato a cui devo giungere e, non solo, sono già anche convinto che quel
risultato sia vero. Si tratta quindi soltanto di trovare la strada giusta per arrivarci
(senza navigatore satellitare
;-)).
Mettendomi nei panni dell'eventuale lettore che non conoscesse il
teorema di Pick, avverto qui che il seguito di questo post riporta la mia dimostrazione
e quindi, se si è interessati a trovarne una potenzialmente diversa, questo è
un buon momento per smettere di leggere.
Dunque...
Innanzitutto cerco il modo per contare i punti interni al poligono date le informazioni
geometriche sui vertici.
Comincio con il definire un sistema di assi cartesiani centrato in un qualunque
punto della griglia che stia più a sinistra e più in basso di tutto il poligono
(suppongo che queste due ultime condizioni siano ininfluenti, ma, visto che posso
scegliere, mi semplifico la vita!).

figura 2
Mi concentro ora nel trovare un modo semplice per esprimere il numero di punti che
stanno "sotto" ad un segmento di Pick. Per "sotto" intendo che hanno ordinata maggiore
o uguale a zero e inferiore al punto di intersezione della verticale con il segmento,
e che inoltre abbiano ascissa compresa (estremi inclusi) tra le ascisse degli estremi
del segmento. Nell'esempio riportato in figura 2 si tratta del numero di punti
evidenziati in giallo.

figura 3
Per fare ciò considero la figura costituita da tutti i punti che stanno
sotto al segmento più tutti quelli che ottengo ruotando la figura di 180° intorno
al punto medio del segmento. Questi punti sono disposti come un rettangolo che chiamo
R (un esempio è riportato in figura 3).
Il numero di punti appartenenti a questo rettangolo è chiaramente dato dal numero
di punti alla base moltiplicato per il numero di punti in altezza.
Chiamando
P1 e
P2
gli estremi del segmento, e chiamando rispettivamente
(x1,
y1) e
(x2,
y2) le loro coordinate, il calcolo del
numero di punti del rettangolo è dato da questa formula:
R = (x2 - x1
+1) * (y2 + y1
+ 1)
Il numero
R calcolato è un numero pari.

figura 4
Infatti, come mostra la figura 4 è possibile scomporre
R in tre rettangoli,
evidenziati dai colori rosso, verde e blu. Chiaramente il rettangolo rosso e quello
blu sono uguali, e quindi contengono lo stesso numero di punti. La somma dei punti
in questi rettangoli è dunque pari. Per dimostrare che
R è un numero pari mi basta
quindi mostrare che il numero di punti nel rettangolo verde è pure pari.
I numeri
dx = x2 - x1
e
dy = y2 - y1
sono numeri primi fra di loro. Infatti, se così non fosse, il segmento tra
P1 e
P2
incontrerebbe altri punti della griglia. Non sarebbe quindi un segmento di Pick,
che per definizione non contiene altri punti della griglia oltre agli estremi. Poiché
dx e
dy sono primi tra loro, almeno uno di essi è dispari (se entrambi fossero
pari avrebbero 2 come divisore comune). Di conseguenza, almeno un valore, tra
dx+1
e
dy+1 è pari. Ne consegue che il loro prodotto è necessariamente pari, e guarda
a caso quel prodotto costituisce appunto il numero di punti del rettangolo verde.
Perciò
R è pari.
Il numero
R è quindi divisibile per 2, e il risultato della divisione è dato dal
numero di punti che stanno "sotto" al segmento più uno. Infatti per costruzione
il numero dei punti appartenenti ad
R che stanno sopra al segmento e quello dei
punti che ne stanno sotto è uguale, ed è uguale alla metà di
R meno i punti che
stanno proprio sul segmento (2).

figura 5
Mi interessa ora trovare il numero di punti che stanno sotto il segmento tranne
quelli dell'ultima colonna (come indicato, nella figura 5, dai punti colorati
di verde). Questo numero, che chiamo
Q, è evidentemente dato da
Q = (R-2)/2 - y2
poiché
y2 è il numero di punti
dell'ultima colonna, e cioè
Q = (x2 - x1
+1) * (y2 + y1
+ 1) / 2 - 1 - y2

figura 6
È facile verificare che questa formula è valida anche se il punto
P1 sta al di sopra del punto
P2
o se hanno la stessa ordinata (cioè
y1
= y2).
Nel caso in cui
P1 stia a destra di
P2 (cioè
x1 >
x2), la formula è ancora valida, salvo
che il risultato è cambiato di segno e viene contato anche il punto estremo coinvolto.
Questo risultato è mostrato dalla figura 6.
In questo caso, infatti, la base del rettangolo
R è la proiezione del segmento
a cui però si escludono gli estremi, invertita di segno. La formula per contarne
i punti
R = (x2 - x1
+1) * (y2 + y1
+ 1)
indica quindi l'inverso del numero di punti di quel rettangolo. Si noti che l'area
vale 0 se
x1 = x2
+ 1. La prima parte della formula di
Q,
(x2
- x1 +1) * (y2
+ y1 + 1) / 2, indica quindi il numero
di punti che stanno sotto al segmento escludendo la prima e l'ultima colonna, come
schematizzato dai punti colorati in verde nella figura 6.

figura 7
La seconda parte della formula
Q,
-1 -y2,
invece, indica chiaramente la colonna a sinistra dei punti che stanno sotto il segmento,
invertita di segno, contando, stavolta, anche il punto
P2
stesso, come mostrato dai punti colorati in blu nella figura 6. La somma algebrica
delle due parti, data dalla formula
Q
Q = (x2 - x1
+1) * (y2 + y1
+ 1) / 2 - 1 - y2
indica dunque il numero dei punti che stanno sotto al segmento, escludendo
la colonna di destra e contando anche l'estremo di sinistra, il tutto invertito
di segno.
La formula
Q mi serve per calcolare, in un concatenamento di segmenti, il
numero dei punti che stanno sotto a quelli che vanno da sinistra a destra, ma contemporaneamente
sopra a quelli che vanno da destra a sinistra. La figura 7 mostra il concatenamento
di due segmenti da sinistra a destra: al numero di punti sotto il segmento rosso
si sommano i punti sotto il segmento blu.

figura 8-1

figura 8-2

figura 8-3
|
Nelle figure 8-1, 8-2, 8-3 viene mostrato il procedimento per sommare algebricamente
i punti relativi a due segmenti consecutivi, uno verso destra e l'altro verso sinistra.
In 8-1 sono mostrati in rosso i punti del segmento rosso, positivi, in 8-2 in blu
i punti del segmento blu, negativi, in 8-3 la loro somma algebrica.

figura 9-1

figura 9-2

figura 9-3

figura 9-4

figura 9-5

figura 9-6
|
Nella sequenza delle figure da 9-1 a 9-6 si vede la procedura reiterata per i segmenti
da P
1-P
2
a P
6-P
1
(chiudendo il giro).
Le figure 9-1 e 9-2 mostrano come si sommino due segmenti verso
destra, la figura 9-3 mostra i punti che vengono sottratti dalla somma ottenuta
al passo precedente. Sono indicati in blu i punti "negativi", cioè quelli che vengono
sottratti in eccesso. Tali punti annullano alcuni di quelli positivi al passo 9-4.
In 9-5 e 9-6 vengono poi sottratti i punti relativi agli ultimi due segmenti, entrambi
verso sinistra.
Il valore che è stato ottenuto dall'iterazione rappresenta il numero di punti interni
al poligono, salvo due punti che vengono sottratti in eccesso (gli estremi
P1 e
P4),
e uno che viene sommato in eccesso (
P3).
Considerando il motivo per cui ciò avviene, si giunge alla conclusione che i punti
sommati in eccesso sono quelli che appartengono ai vertici delle "concavità a sinistra"
(cioè quelli che formano una concavità tra un segmento verso destra e il successivo
verso sinistra), e, viceversa, i punti sottratti in eccesso sono quelli che appartengono
ai vertici delle "convessità a sinistra" (cioè quelli che formano una convessità
tra il segmento precedente verso sinistra e il successivo verso destra).
È facile dimostrare che, percorrendo un poligono in senso orario, il numero totale
di vertici a concavità a sinistra è uguale al numero di vertici a convessità
a sinistra meno uno, infatti, ad ogni "cambio di direzione", percorrendo il perimetro
del poligono, deve prima o poi seguire un cambio di direzione nel verso opposto.
Quindi per calcolare il numero esatto dei punti interni al poligono, se N e' il numero di
convessita' a sinistra bisogna sommare N e sottrarre N-1, ovvero sommare 1.
Riprendendo la formula per
Q, e generalizzandola sugli indici dei punti:
Qi = (xi+1
- xi +1) * (yi+1
+ yi + 1) / 2 - 1 - yi+1
Questa vale per tutti gli
n segmenti del poligono, facendo variare
i sui
valori
1, 2, ..., n. L'indice
n+1 identifica il punto
P1, in modo che l'ultimo segmento
sia quello che congiunge
Pn con
P1.
Modifico un po' la formula, moltiplicando e raccogliendo:
Qi = (xi+1
- xi) * (yi+1
+ yi) / 2 + (xi+1
- xi + yi+1
+ yi + 1)/2 - 1 - yi+1
ottenendo, poi
Qi = (xi+1
- xi) * (yi+1
+ yi) / 2 + (xi+1
- xi -yi+1
+ yi - 1)/2
Posso spezzare in due questa formula, chiamando
Ai = (xi+1
- xi) * (yi+1
+ yi) / 2
Bi = (xi+1
- xi -yi+1
+ yi - 1)/2
e dunque
Qi = Ai
+ Bi
Il numero dei punti interni del poligono è quindi dato da
PI = (Σi
= 1..nQi) +1 = [Σi
= 1..n(Ai + Bi)]
+1
ovvero:
PI = (Σi
= 1..nAi) + (Σi
= 1..nBi) +1
Detti
A = Σi = 1..nAi
B = Σi = 1..nBi
si conclude che
PI = A + B + 1
La parte
B si può semplificare. Infatti
B = Σi = 1..nBi
= Σi = 1..n[(xi+1
- xi -yi+1
+ yi - 1)/2]
o, in altre parole
B = [(x2-x1-y2+y1-1)
+ (x3-x2-y3+y2-1)
+ ... + (xn-xn-1-yn+yn-1-1)
+ (x1-xn-y1+yn-1)]/2
Osservando la formula così scritta si nota che tutti i termini
xi
e
yi si semplificano tra loro, e quel che
rimane è
-1 sommato
n volte,
dove
n è il numero dei lati del poligono, che equivale
evidentemente al numero dei punti che stanno sul contorno del poligono. Quindi
B = -PC/2
e, di conseguenza
PI = A - PC/2
+ 1
Cerco ora di calcolare l'area del poligono di Pick.

figura 10
In modo simile a quanto fatto sopra, considero il poligono di Pick segmento per
segmento. Ogni segmento, se percorso da sinsitra verso destra, dà un contributo
positivo dato dall'area del trapezio formato dal segmento stesso e dalla sua proiezione
sull'asse delle ascisse, come esemplificato nella figura 10. L'area del trapezio
è data dalla somma delle basi (
y1 + y2) per l'altezza (
x2
- x1) diviso
2.
Generalizzando, dunque
Ai = (xi+1
- xi) * (yi+1
+ yi) / 2
Questa formula vale anche per i segmenti percorsi da destra verso sinistra, salvo
il fatto che l'area ottenuta è cambiata di segno, visto che l'altezza (
xi+1
- xi) è negativa. La somma algebrica dei
contributi di tutti i segmenti comunque vengano percorsi, genera l'area del poligono,
come esemplificato dalla sequenza delle figure da 11-1 a 11-6.

figura 11-1

figura 11-2

figura 11-3

figura 11-4

figura 11-5

figura 11-6
|
Ad ogni passo della
sequenza si somma algebricamente la porzione
Ai relativa al segmento in questione.
Nella figura 11-3 è evidenzata in blu la porzione che viene sottratta in eccesso,
e che poi viene ricompensata dall'area positiva sommata al passo 11-4.
La sommatoria
Σi=1..n Ai
che quindi rappresenta l'area del poligono, è proprio uguale alla porzione
A della formula ottenuta sopra
PI = A - PC/2
+ 1
Elaborando la precedente si ottiene dunque
A = PI + PC/2
- 1
che rappresenta proprio il teorema di Pick.
Ai miei tempi, a questo punto, si concludeva l'esercizio, godendosi il momento di agoniata gloria,
con l'acronimo
CVD