Analizzando l’algoritmo e con l’aiuto dell’implementazione è stata verificata l’esistenza di al- cuni casi in cui l’algoritmo ACE non è in grado di garantire la correttezza della triangolazione di Delaunay distribuita in uno spazio a due dimensioni considerando join sequenziali. In particolare, è possibile che alcuni nodi che effettuano la join in una rete con una triango- lazione corretta al tempo t non vengano a conoscenza di tutti i loro vicini, quindi esistono alcuni casi in cui il teorema di correttezza 4.2.3 non sia corretto. In particolare si consideri il seguente esempio:
Esempio. Si consideri la seguente triangolazione di Delaunay al tempo t (descritta in Figura 4.11) calcolata su S = {1, 2, 3, 4}. Si supponga che al tempo t la triangolazione di Delaunay sia corretta, e che quindi valgano le seguenti condizioni:
• N (1) = {2, 3}; {1, 2, 3} ⊂ C(1); {1, 2, 3} ⊂ N (1)queried;
• N (2) = {1, 3, 4}; C(2) = S; N (2)queried = S;
• N (3) = {1, 2, 4}; C(3) = S; N (3)queried = S;
• N (4) = {2, 3}; {2, 3, 4} ⊂ C(4); {2, 3, 4} ⊂ Nqueried(4);
Ora supponiamo che al tempo t + 1 un nuovo nodo 5 intenda entrare nella rete e posizio- narsi come mostrato in Figura 4.12.
Appena entrato nella rete, il nodo 5 contatta il nodo di bootstrap per venire a co- noscenza del nodo più vicino a lui nella rete, il quale è il nodo 3. Quindi, 5 invia a 3 una N eighborSetRequest e aggiorna la propria Candidate Set e la Neighbor Querried Set (C(5) = {3, 5}, Nqueried(5) = {3}).
Il nodo 3, che riceve il messaggio, aggiunge 5 alla Candidate Set (C(3) = {1, 2, 3, 4, 5}) e calcola i suoi nuovi vicini nella triangolazione di Delaunay DT (C(3)), i quali risultano essere come mostrato in Figura 4.13 N (3) = {2, 4, 5}.
Figura 4.11: La triangolazione di Delaunay su S al tempo t .
Il nodo 3, quindi, calcola i vicini comuni tra 3 e 5 in DT (C(3)) e li invia a 5 tramite il messaggio N eighborSetReply. Si noti che la triangolazione DT (C(3)) è corretta e coincide con la triangolazione di Delaunay su S, perché C(3) = S. I nodi che vengono inclusi nel messaggio N eighborSetReply sono N (5)mutual3,5 (3) = {2, 4}. Si noti anche che a causa del flip dell’arco che collegava 3 e 1, il nodo 1 non viene notificato a 5.
Quando 5 riceve il messaggio N eighborSetReply, aggiunge i nuovi nodi 2 e 4 alla sua Candidate Set (C(5) = {2, 3, 4, 5}) e aggiorna la propria triangolazione di Delaunay locale (DT (C(5))), come mostrato in Figura 4.14.
Quindi, il nodo 5 esegue la procedura U pdate_neighbors: si ricorda che in tale proce- dura vengono distinti i triangoli che non contengono alcun nodo in Nqueried(5) dagli altri in DT (C(5)), e da questi triangoli viene preso un nuovo nodo per triangolo a cui invia- re una N eighborSetRequest, mentre agli altri nuovi nodi sarà inviata una semplice notifica N eighborN otif ication. Poiché tutti e 3 i triangoli della triangolazione di Delaunay DT (C(5)) includono il nodo 3, il quale è in Nqueried(5), tutti i triangoli della triangolazione calcolata sono stati già selezionati, quindi nessuno dei nodi nuovi (Nnew(5) = {2, 3, 4}) è un nodo checked.
Figura 4.12: Il nuovo nodo 5 posizionato nella rete .
• C(5) = {2, 3, 4, 5} • N (5) = {2, 3, 4} • Nqueried(5) = {3}
Quindi, i nodi notify sono 2 e 4, mentre non esistono nodi in Ncheck(5). 5 invia quindi a 2 e a 4 una N eighborN otif ication.
Nello step successivo, 2 e 4 ricevono una N eighborN otif ication da parte di 5, quindi aggiun- gono 5 a C(2) e C(4) e aggiornano N (2) e N (4) calcolando la triangolazione sulle Candidate Set. L’algoritmo cosi termina, lasciando la triangolazione distribuita in uno stato errato, poiché ne il nodo 5 ne 1 sono venuti a conoscenza l’uno dell’altro. La Figura 4.3 mostra la triangolazione distribuita calcolata al termine della procedura di join del nodo 5: il numero di errori totale è 2. Questo problema si ripercuote anche sugli inserimenti successivi, che non trovando una triangolazione corretta non riescono a loro volta a costruire una triangolazione di Delaunay locale corretta.
Figura 4.13: La triangolazione di Delaunay DT (C(3)) dopo l’aggiunta del nodo 5 a C(3) .
Figura 4.14: La triangolazione di Delaunay DT (C(5)) dopo la ricezione di N eighborSetReply(N (5)mutual
3,5 (3))
Figura 4.15: In ordine dall’alto verso il basso, da sinistra a destra: le triangolazioni di Delaunay al termine della procedura di join del nodo 5 calcolate in C(1), C(2), C(3), C(4), C(5)
.
Analisi del problema. È stata quindi effettuata un analisi sul teorema di correttezza (Teorema 4.2.3) e dei Lemmi 4.2.1 e 4.2.2 al fine di verificare il corretto funzionamento della procedura di join sequenziale. Nell’analisi effettuata, si è trovata un’assunzione errata relativa al punto 4 della dimostrazione, il quale identifica un triangolo T intersecato dalla linea retta che collega il nuovo vicino non ancora aggiunto v con il nodo n che stiamo considerando. Secondo Lee et al. in [21], tale triangolo esiste sempre: questo è verificato essere non sempre vero. Si consideri, ad esempio, l’esempio presentato precedentemente, il quale nonostante la sequenzialità della procedura di join del nodo 5 termina con 2 errori, poiché il nodo 5 e 1 non vengono a conoscenza l’uno dell’altro. Adattando la dimostrazione del Lemma 4.2.2, il nostro nodo n è il nodo 1, mentre il nodo v è il nostro 5: supponiamo inoltre che il nodo 5 abbia già inviato la N eighborSetRequest a 3 e che abbia già ricevuto la N eighborSetReply e abbia già calcolato la triangolazione di Delaunay in C(5).
A questo punto, consideriamo la linea retta l che congiunge 5 a 1, così come mostrato in 4.16.
Figura 4.16: In figura: La linea retta tracciata da 1 a 5 non attraversa alcun triangolo nella triangolazione DT (C(5))
.
Secondo il punto 4 della dimostrazione del Lemma 4.2.2, l dovrebbe intersecare un trian- golo nella triangolazione di Delaunay DT (C(5)), ma come si evince dalla Figura 4.16, questo non è vero in questo caso. Quindi, non è possibile applicare il Lemma 4.2.1, e di conseguenza l’algoritmo di join termina senza che il nodo 5 venga a conoscenza di tutti i suoi vicini di Delaunay, in particolare del nodo 1.
Elaborazione di una soluzione. A causa dei problemi individuati grazie all’analisi effet- tuata, è nata l’esigenza di elaborare un nuovo algoritmo che, a differenza di ACE, utilizza un numero maggiore di messaggi, ma raggiunge l’accuratezza del 100%. Tale algoritmo sarà descritto nel prossimo paragrafo.