Triangulari
Mihai-Sorin Stupariu
Sem. I, 2016 - 2017
Triangulari 1 / 17
Triangularea poligoanelor. Problema galeriei de arta
Supravegherea unei galerii de artaCamera din P poate supraveghea A, dar nu B.
����
rJJJJJJJ
P
rA
rB
Triangulari 2 / 17
Triangularea poligoanelor. Problema galeriei de arta
Formalizare
I O galerie de arta poate fi interpretata (ın contextul acestei probleme)ca un poligon simplu P (adica un poligon fara autointersectii) avandn varfuri.
I O camera video (vizibilitate 3600) poate fi identificata cu un punctdin interiorul lui P; ea poate supraveghea acele puncte cu care poatefi unita printr-un segment inclus ın interiorul poligonului.
I Problema galeriei de arta: cate camere video sunt necesare pentrua supraveghea o galerie de arta si unde trebuie amplasate acestea?
Triangulari 3 / 17
Triangularea poligoanelor. Problema galeriei de arta
Formalizare
I O galerie de arta poate fi interpretata (ın contextul acestei probleme)ca un poligon simplu P (adica un poligon fara autointersectii) avandn varfuri.
I O camera video (vizibilitate 3600) poate fi identificata cu un punctdin interiorul lui P; ea poate supraveghea acele puncte cu care poatefi unita printr-un segment inclus ın interiorul poligonului.
I Problema galeriei de arta: cate camere video sunt necesare pentrua supraveghea o galerie de arta si unde trebuie amplasate acestea?
Triangulari 3 / 17
Triangularea poligoanelor. Problema galeriei de arta
Formalizare
I O galerie de arta poate fi interpretata (ın contextul acestei probleme)ca un poligon simplu P (adica un poligon fara autointersectii) avandn varfuri.
I O camera video (vizibilitate 3600) poate fi identificata cu un punctdin interiorul lui P; ea poate supraveghea acele puncte cu care poatefi unita printr-un segment inclus ın interiorul poligonului.
I Problema galeriei de arta: cate camere video sunt necesare pentrua supraveghea o galerie de arta si unde trebuie amplasate acestea?
Triangulari 3 / 17
Triangularea poligoanelor. Problema galeriei de arta
Numarul de camere vs. forma poligonului
I Se doreste exprimarea numarului de camere necesare pentrusupraveghere ın functie de n (sau controlarea acestuia de catre n).
I Pentru a supraveghea un spatiu avand forma unui poligon convex,este suficienta o singura camera.
I Numarul de camere depinde si de forma poligonului: cu cat formaeste mai ”complexa”, cu atat numarul de camere va fi mai mare.
I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).
Triangulari 4 / 17
Triangularea poligoanelor. Problema galeriei de arta
Numarul de camere vs. forma poligonului
I Se doreste exprimarea numarului de camere necesare pentrusupraveghere ın functie de n (sau controlarea acestuia de catre n).
I Pentru a supraveghea un spatiu avand forma unui poligon convex,este suficienta o singura camera.
I Numarul de camere depinde si de forma poligonului: cu cat formaeste mai ”complexa”, cu atat numarul de camere va fi mai mare.
I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).
Triangulari 4 / 17
Triangularea poligoanelor. Problema galeriei de arta
Numarul de camere vs. forma poligonului
I Se doreste exprimarea numarului de camere necesare pentrusupraveghere ın functie de n (sau controlarea acestuia de catre n).
I Pentru a supraveghea un spatiu avand forma unui poligon convex,este suficienta o singura camera.
I Numarul de camere depinde si de forma poligonului: cu cat formaeste mai ”complexa”, cu atat numarul de camere va fi mai mare.
I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).
Triangulari 4 / 17
Triangularea poligoanelor. Problema galeriei de arta
Numarul de camere vs. forma poligonului
I Se doreste exprimarea numarului de camere necesare pentrusupraveghere ın functie de n (sau controlarea acestuia de catre n).
I Pentru a supraveghea un spatiu avand forma unui poligon convex,este suficienta o singura camera.
I Numarul de camere depinde si de forma poligonului: cu cat formaeste mai ”complexa”, cu atat numarul de camere va fi mai mare.
I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).
Triangulari 4 / 17
Triangularea poligoanelor. Problema galeriei de arta
Definitii
I Fie P un poligon plan.
I (i) O diagonala a lui P este un segment ce uneste doua varfuri aleacestuia si care este situat ın interiorul lui P.
I (ii) O triangulare TP a lui P este o descompunere a lui P ıntriunghiuri, data de o multime maximala de diagonale ce nu seintersecteaza.
I Teorema. Orice poligon simplu admite o triangulare. Oricetriangulare a unui poligon cu n varfuri contine exact n− 2 triunghiuri.
Triangulari 5 / 17
Triangularea poligoanelor. Problema galeriei de arta
Definitii
I Fie P un poligon plan.
I (i) O diagonala a lui P este un segment ce uneste doua varfuri aleacestuia si care este situat ın interiorul lui P.
I (ii) O triangulare TP a lui P este o descompunere a lui P ıntriunghiuri, data de o multime maximala de diagonale ce nu seintersecteaza.
I Teorema. Orice poligon simplu admite o triangulare. Oricetriangulare a unui poligon cu n varfuri contine exact n− 2 triunghiuri.
Triangulari 5 / 17
Triangularea poligoanelor. Problema galeriei de arta
Definitii
I Fie P un poligon plan.
I (i) O diagonala a lui P este un segment ce uneste doua varfuri aleacestuia si care este situat ın interiorul lui P.
I (ii) O triangulare TP a lui P este o descompunere a lui P ıntriunghiuri, data de o multime maximala de diagonale ce nu seintersecteaza.
I Teorema. Orice poligon simplu admite o triangulare. Oricetriangulare a unui poligon cu n varfuri contine exact n− 2 triunghiuri.
Triangulari 5 / 17
Triangularea poligoanelor. Problema galeriei de arta
Definitii
I Fie P un poligon plan.
I (i) O diagonala a lui P este un segment ce uneste doua varfuri aleacestuia si care este situat ın interiorul lui P.
I (ii) O triangulare TP a lui P este o descompunere a lui P ıntriunghiuri, data de o multime maximala de diagonale ce nu seintersecteaza.
I Teorema. Orice poligon simplu admite o triangulare. Oricetriangulare a unui poligon cu n varfuri contine exact n− 2 triunghiuri.
Triangulari 5 / 17
Triangularea poligoanelor. Problema galeriei de arta
Rezovlarea problemei galeriei de arta
I Amplasarea camerelor se poate face ın varfurile poligonului.
I Data o pereche (P, TP) se considera o 3-colorare a acesteia: fiecaruivarf ıi corespunde o culoare dintr-un set de 3 culori si pentru fiecaretriunghi, cele 3 varfuri au culori distincte.
I Observatie. Daca P este simplu, o astfel de colorare exista, deoarecegraful asociat perechii (P, TP) este arbore.
Triangulari 6 / 17
Triangularea poligoanelor. Problema galeriei de arta
Rezovlarea problemei galeriei de arta
I Amplasarea camerelor se poate face ın varfurile poligonului.
I Data o pereche (P, TP) se considera o 3-colorare a acesteia: fiecaruivarf ıi corespunde o culoare dintr-un set de 3 culori si pentru fiecaretriunghi, cele 3 varfuri au culori distincte.
I Observatie. Daca P este simplu, o astfel de colorare exista, deoarecegraful asociat perechii (P, TP) este arbore.
Triangulari 6 / 17
Triangularea poligoanelor. Problema galeriei de arta
Rezovlarea problemei galeriei de arta
I Amplasarea camerelor se poate face ın varfurile poligonului.
I Data o pereche (P, TP) se considera o 3-colorare a acesteia: fiecaruivarf ıi corespunde o culoare dintr-un set de 3 culori si pentru fiecaretriunghi, cele 3 varfuri au culori distincte.
I Observatie. Daca P este simplu, o astfel de colorare exista, deoarecegraful asociat perechii (P, TP) este arbore.
Triangulari 6 / 17
Triangularea poligoanelor. Problema galeriei de arta
Teorema galeriei de arta
I Teorema. [Chvatal, 1975; Fisk, 1978] Pentru un poligon cu n varfuri,[n3
]camere sunt uneori necesare si ıntotdeauna suficiente pentru ca
fiecare punct al poligonului sa fie vizibil din cel putin una din camere.
Triangulari 7 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,
I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];
I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: ear cutting / clipping / trimming
I Concepte:
I varf principal,I ear (varf / componenta de tip E) [Meisters, 1975];I mouth (varf / componenta de tip M) [Toussaint, 1991].
I Orice varf de tip E este convex; orice varf de tip M este concav (reflex). Reciprocnu neaparat!
I Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu cel putin 4varfuri admite cel putin doua componente de tip E care nu se suprapun.
I Corolar. Orice poligon simplu admite (cel putin) doua diagonale.
I Gasirea unei componente de tip E : complexitate O(n) [ElGindy, Everett,Toussaint, 1993]. Se bazeaza pe Two Ears Theorem!
I Algoritmul de triangulare bazat de metoda ear cutting: complexitate O(n2).
I Link despre triangulariLink pentru algoritmul Ear cutting
Triangulari 8 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: descompunerea ın poligoanemonotone
I Concept: poligon y-monoton
I Algoritmi de triangulare eficienti: complexitate O(n) pentru poligoaney -monotone [Garey et al., 1978].
I Descompunerea unui poligon oarecare in componente y -monotonepoate fi realizata cu un algoritm de complexitate O(n log n) [Lee,Preparata, 1977].
I Exista si alte clase de algoritmi mai rapizi; [Chazelle, 1990]: algoritmliniar.
I Link pentru alte abordari
Triangulari 9 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: descompunerea ın poligoanemonotone
I Concept: poligon y-monoton
I Algoritmi de triangulare eficienti: complexitate O(n) pentru poligoaney -monotone [Garey et al., 1978].
I Descompunerea unui poligon oarecare in componente y -monotonepoate fi realizata cu un algoritm de complexitate O(n log n) [Lee,Preparata, 1977].
I Exista si alte clase de algoritmi mai rapizi; [Chazelle, 1990]: algoritmliniar.
I Link pentru alte abordari
Triangulari 9 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: descompunerea ın poligoanemonotone
I Concept: poligon y-monoton
I Algoritmi de triangulare eficienti: complexitate O(n) pentru poligoaney -monotone [Garey et al., 1978].
I Descompunerea unui poligon oarecare in componente y -monotonepoate fi realizata cu un algoritm de complexitate O(n log n) [Lee,Preparata, 1977].
I Exista si alte clase de algoritmi mai rapizi; [Chazelle, 1990]: algoritmliniar.
I Link pentru alte abordari
Triangulari 9 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: descompunerea ın poligoanemonotone
I Concept: poligon y-monoton
I Algoritmi de triangulare eficienti: complexitate O(n) pentru poligoaney -monotone [Garey et al., 1978].
I Descompunerea unui poligon oarecare in componente y -monotonepoate fi realizata cu un algoritm de complexitate O(n log n) [Lee,Preparata, 1977].
I Exista si alte clase de algoritmi mai rapizi; [Chazelle, 1990]: algoritmliniar.
I Link pentru alte abordari
Triangulari 9 / 17
Triangularea poligoanelor. Problema galeriei de arta
Metode de triangulare: descompunerea ın poligoanemonotone
I Concept: poligon y-monoton
I Algoritmi de triangulare eficienti: complexitate O(n) pentru poligoaney -monotone [Garey et al., 1978].
I Descompunerea unui poligon oarecare in componente y -monotonepoate fi realizata cu un algoritm de complexitate O(n log n) [Lee,Preparata, 1977].
I Exista si alte clase de algoritmi mai rapizi; [Chazelle, 1990]: algoritmliniar.
I Link pentru alte abordari
Triangulari 9 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S
6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S
8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S
9. extrage celelalte varfuri din S daca diagonalele formate cu vjsunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S
11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea poligoanelor. Problema galeriei de arta
Triangularea poligoanelor monotone
Input: Un poligon y -monoton P.Output: O triangulare a lui P.
1. Lantul varfurilor din partea stanga si al celor din partea dreapta sunt unite ıntr-unsingur sir, ordonat descrescator, dupa y (daca ordonata este egala, se folosesteabscisa). Fie v1, v2, . . . , vn sirul ordonat.
2. Initializeaza o stiva vida S si insereaza v1, v2.
3. for j = 3 to n − 1
4. do if vj si varful din top al lui S sunt ın lanturi diferite
5. then extrage toate varfurile din S6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul
7. insereaza vj−1 si vj ın S8. else extrage un varf din S9. extrage celelalte varfuri din S daca diagonalele formate cu vj
sunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras
10. insereaza vj ın S11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)
Triangulari 10 / 17
Triangularea unei multimi arbitrare de puncte
Problematizare
I Triangularea unui poligon convex (lista ordonata de puncte(P1,P2, . . . ,Pn).
I Are sens sa vorbim de triangulare pentru multimea {P1,P2, . . . ,Pn}?I Comentariu: Triangularile multimilor de puncte sunt esentiale ın
grafica pe calculator.
I Definitie. O triangulare a unei multimi P din plan este o subdivizaremaximala a acoperirii convexe Conv(P) a lui P cu triunghiuri alecaror varfuri sunt elemente ale lui P (fara autointersectii!)
I Trebuie facuta distinctie ıntre triangulare a unui poligon(P1,P2, . . . ,Pn) si triangulare a multimii subdiacente{P1,P2, . . . ,Pn} (coincid daca poligonul este convex!)
Triangulari 11 / 17
Triangularea unei multimi arbitrare de puncte
Problematizare
I Triangularea unui poligon convex (lista ordonata de puncte(P1,P2, . . . ,Pn).
I Are sens sa vorbim de triangulare pentru multimea {P1,P2, . . . ,Pn}?
I Comentariu: Triangularile multimilor de puncte sunt esentiale ıngrafica pe calculator.
I Definitie. O triangulare a unei multimi P din plan este o subdivizaremaximala a acoperirii convexe Conv(P) a lui P cu triunghiuri alecaror varfuri sunt elemente ale lui P (fara autointersectii!)
I Trebuie facuta distinctie ıntre triangulare a unui poligon(P1,P2, . . . ,Pn) si triangulare a multimii subdiacente{P1,P2, . . . ,Pn} (coincid daca poligonul este convex!)
Triangulari 11 / 17
Triangularea unei multimi arbitrare de puncte
Problematizare
I Triangularea unui poligon convex (lista ordonata de puncte(P1,P2, . . . ,Pn).
I Are sens sa vorbim de triangulare pentru multimea {P1,P2, . . . ,Pn}?I Comentariu: Triangularile multimilor de puncte sunt esentiale ın
grafica pe calculator.
I Definitie. O triangulare a unei multimi P din plan este o subdivizaremaximala a acoperirii convexe Conv(P) a lui P cu triunghiuri alecaror varfuri sunt elemente ale lui P (fara autointersectii!)
I Trebuie facuta distinctie ıntre triangulare a unui poligon(P1,P2, . . . ,Pn) si triangulare a multimii subdiacente{P1,P2, . . . ,Pn} (coincid daca poligonul este convex!)
Triangulari 11 / 17
Triangularea unei multimi arbitrare de puncte
Problematizare
I Triangularea unui poligon convex (lista ordonata de puncte(P1,P2, . . . ,Pn).
I Are sens sa vorbim de triangulare pentru multimea {P1,P2, . . . ,Pn}?I Comentariu: Triangularile multimilor de puncte sunt esentiale ın
grafica pe calculator.
I Definitie. O triangulare a unei multimi P din plan este o subdivizaremaximala a acoperirii convexe Conv(P) a lui P cu triunghiuri alecaror varfuri sunt elemente ale lui P (fara autointersectii!)
I Trebuie facuta distinctie ıntre triangulare a unui poligon(P1,P2, . . . ,Pn) si triangulare a multimii subdiacente{P1,P2, . . . ,Pn} (coincid daca poligonul este convex!)
Triangulari 11 / 17
Triangularea unei multimi arbitrare de puncte
Problematizare
I Triangularea unui poligon convex (lista ordonata de puncte(P1,P2, . . . ,Pn).
I Are sens sa vorbim de triangulare pentru multimea {P1,P2, . . . ,Pn}?I Comentariu: Triangularile multimilor de puncte sunt esentiale ın
grafica pe calculator.
I Definitie. O triangulare a unei multimi P din plan este o subdivizaremaximala a acoperirii convexe Conv(P) a lui P cu triunghiuri alecaror varfuri sunt elemente ale lui P (fara autointersectii!)
I Trebuie facuta distinctie ıntre triangulare a unui poligon(P1,P2, . . . ,Pn) si triangulare a multimii subdiacente{P1,P2, . . . ,Pn} (coincid daca poligonul este convex!)
Triangulari 11 / 17
Triangularea unei multimi arbitrare de puncte
Elemente ale unei triangulari
I Data o multime de puncte P si o triangulare TP a sa:varfuri, muchii, triunghiuri.
I Legatura ıntre aceste elemente?
I Propozitie. Fie P o multime de n puncte din plan nesituate toate peo aceeasi dreapta. Notam cu k numarul de puncte de pe frontieraacoperirii convexe Conv(P). Orice triangulare a lui P are(2n − k − 2) triunghiuri si (3n − k − 3) muchii.
I Demonstratie: Se bazeaza pe formula lui Euler / numarul deincidente.
I Exemplu: Cazul unui poligon convex cu n varfuri (k = n): n − 2triunghiuri si 2n − 3 muchii.
Triangulari 12 / 17
Triangularea unei multimi arbitrare de puncte
Elemente ale unei triangulari
I Data o multime de puncte P si o triangulare TP a sa:varfuri, muchii, triunghiuri.
I Legatura ıntre aceste elemente?
I Propozitie. Fie P o multime de n puncte din plan nesituate toate peo aceeasi dreapta. Notam cu k numarul de puncte de pe frontieraacoperirii convexe Conv(P). Orice triangulare a lui P are(2n − k − 2) triunghiuri si (3n − k − 3) muchii.
I Demonstratie: Se bazeaza pe formula lui Euler / numarul deincidente.
I Exemplu: Cazul unui poligon convex cu n varfuri (k = n): n − 2triunghiuri si 2n − 3 muchii.
Triangulari 12 / 17
Triangularea unei multimi arbitrare de puncte
Elemente ale unei triangulari
I Data o multime de puncte P si o triangulare TP a sa:varfuri, muchii, triunghiuri.
I Legatura ıntre aceste elemente?
I Propozitie. Fie P o multime de n puncte din plan nesituate toate peo aceeasi dreapta. Notam cu k numarul de puncte de pe frontieraacoperirii convexe Conv(P). Orice triangulare a lui P are(2n − k − 2) triunghiuri si (3n − k − 3) muchii.
I Demonstratie: Se bazeaza pe formula lui Euler / numarul deincidente.
I Exemplu: Cazul unui poligon convex cu n varfuri (k = n): n − 2triunghiuri si 2n − 3 muchii.
Triangulari 12 / 17
Triangularea unei multimi arbitrare de puncte
Elemente ale unei triangulari
I Data o multime de puncte P si o triangulare TP a sa:varfuri, muchii, triunghiuri.
I Legatura ıntre aceste elemente?
I Propozitie. Fie P o multime de n puncte din plan nesituate toate peo aceeasi dreapta. Notam cu k numarul de puncte de pe frontieraacoperirii convexe Conv(P). Orice triangulare a lui P are(2n − k − 2) triunghiuri si (3n − k − 3) muchii.
I Demonstratie: Se bazeaza pe formula lui Euler / numarul deincidente.
I Exemplu: Cazul unui poligon convex cu n varfuri (k = n): n − 2triunghiuri si 2n − 3 muchii.
Triangulari 12 / 17
Triangularea unei multimi arbitrare de puncte
Elemente ale unei triangulari
I Data o multime de puncte P si o triangulare TP a sa:varfuri, muchii, triunghiuri.
I Legatura ıntre aceste elemente?
I Propozitie. Fie P o multime de n puncte din plan nesituate toate peo aceeasi dreapta. Notam cu k numarul de puncte de pe frontieraacoperirii convexe Conv(P). Orice triangulare a lui P are(2n − k − 2) triunghiuri si (3n − k − 3) muchii.
I Demonstratie: Se bazeaza pe formula lui Euler / numarul deincidente.
I Exemplu: Cazul unui poligon convex cu n varfuri (k = n): n − 2triunghiuri si 2n − 3 muchii.
Triangulari 12 / 17
Triangulari unghiular optime
Problematizare
I Problema. Se fac masuratori ale altitidinii pentru un teren. Sedoreste reprezentarea tridimensionala (cat mai sugestiva). Alternativ:se doreste generarea unui teren pentru o aplicatie.
Triangulari 13 / 17
Triangulari unghiular optime
Problematizare
I Problema. Se fac masuratori ale altitidinii pentru un teren. Sedoreste reprezentarea tridimensionala (cat mai sugestiva). Alternativ:se doreste generarea unui teren pentru o aplicatie.
Triangulari 13 / 17
Triangulari unghiular optime
Problematizare
I Problema. Se fac masuratori ale altitidinii pentru un teren. Sedoreste reprezentarea tridimensionala (cat mai sugestiva). Alternativ:se doreste generarea unui teren pentru o aplicatie.
Triangulari 13 / 17
Triangulari unghiular optime
Problematizare - continuareI Problema (reformulata). Cum ”comparam triangularile” unei
multimi de puncte fixate?
I Exemplu. Masuratori ale altitudinii.
Triangulare 1
1000
980
990
1005
640
620
630
580
570
590
Triangulare 2
1000
980
990
1005
640
620
630
580
570
590
I Intrebari naturale: (i) Exista o triangulare “convenabila” a uneimultimi de puncte? (ii) Cum poate fi determinata eficient o astfel detriangulare?
Triangulari 14 / 17
Triangulari unghiular optime
Problematizare - continuareI Problema (reformulata). Cum ”comparam triangularile” unei
multimi de puncte fixate?I Exemplu. Masuratori ale altitudinii.
Triangulare 1
1000
980
990
1005
640
620
630
580
570
590
Triangulare 2
1000
980
990
1005
640
620
630
580
570
590
I Intrebari naturale: (i) Exista o triangulare “convenabila” a uneimultimi de puncte? (ii) Cum poate fi determinata eficient o astfel detriangulare?
Triangulari 14 / 17
Triangulari unghiular optime
Problematizare - continuareI Problema (reformulata). Cum ”comparam triangularile” unei
multimi de puncte fixate?I Exemplu. Masuratori ale altitudinii.
Triangulare 1
1000
980
990
1005
640
620
630
580
570
590
Triangulare 2
1000
980
990
1005
640
620
630
580
570
590
I Intrebari naturale: (i) Exista o triangulare “convenabila” a uneimultimi de puncte? (ii) Cum poate fi determinata eficient o astfel detriangulare?
Triangulari 14 / 17
Triangulari unghiular optime
Terminologie
I Fixata: o multime de puncte P.
I Fie T o triangulare a lui P cu m triunghiuri. Fie α1, α2, . . . , α3m
unghiurile lui T , ordonate crescator. Vectorul unghiurilor lui T esteA(T ) = (α1, α2, . . . , α3m).
I Relatie de ordine pe multimea triangularilor lui P: ordinealexicografica pentru vectorii unghiurilor. Fie T si T ′ doua triangulariale lui P. Atunci A(T ) > A(T ′) daca ∃i astfel ca αj = α′
j , ∀1 ≤ j < isi αi > α′
i .
I Triangulare unghiular optima: T astfel ca A(T ) ≥ A(T ′), pentruorice triangulare T ′.
I Exemplu: Cazul unui patrulater convex.
Triangulari 15 / 17
Triangulari unghiular optime
Terminologie
I Fixata: o multime de puncte P.
I Fie T o triangulare a lui P cu m triunghiuri. Fie α1, α2, . . . , α3m
unghiurile lui T , ordonate crescator. Vectorul unghiurilor lui T esteA(T ) = (α1, α2, . . . , α3m).
I Relatie de ordine pe multimea triangularilor lui P: ordinealexicografica pentru vectorii unghiurilor. Fie T si T ′ doua triangulariale lui P. Atunci A(T ) > A(T ′) daca ∃i astfel ca αj = α′
j , ∀1 ≤ j < isi αi > α′
i .
I Triangulare unghiular optima: T astfel ca A(T ) ≥ A(T ′), pentruorice triangulare T ′.
I Exemplu: Cazul unui patrulater convex.
Triangulari 15 / 17
Triangulari unghiular optime
Terminologie
I Fixata: o multime de puncte P.
I Fie T o triangulare a lui P cu m triunghiuri. Fie α1, α2, . . . , α3m
unghiurile lui T , ordonate crescator. Vectorul unghiurilor lui T esteA(T ) = (α1, α2, . . . , α3m).
I Relatie de ordine pe multimea triangularilor lui P: ordinealexicografica pentru vectorii unghiurilor. Fie T si T ′ doua triangulariale lui P. Atunci A(T ) > A(T ′) daca ∃i astfel ca αj = α′
j , ∀1 ≤ j < isi αi > α′
i .
I Triangulare unghiular optima: T astfel ca A(T ) ≥ A(T ′), pentruorice triangulare T ′.
I Exemplu: Cazul unui patrulater convex.
Triangulari 15 / 17
Triangulari unghiular optime
Terminologie
I Fixata: o multime de puncte P.
I Fie T o triangulare a lui P cu m triunghiuri. Fie α1, α2, . . . , α3m
unghiurile lui T , ordonate crescator. Vectorul unghiurilor lui T esteA(T ) = (α1, α2, . . . , α3m).
I Relatie de ordine pe multimea triangularilor lui P: ordinealexicografica pentru vectorii unghiurilor. Fie T si T ′ doua triangulariale lui P. Atunci A(T ) > A(T ′) daca ∃i astfel ca αj = α′
j , ∀1 ≤ j < isi αi > α′
i .
I Triangulare unghiular optima: T astfel ca A(T ) ≥ A(T ′), pentruorice triangulare T ′.
I Exemplu: Cazul unui patrulater convex.
Triangulari 15 / 17
Triangulari unghiular optime
Terminologie
I Fixata: o multime de puncte P.
I Fie T o triangulare a lui P cu m triunghiuri. Fie α1, α2, . . . , α3m
unghiurile lui T , ordonate crescator. Vectorul unghiurilor lui T esteA(T ) = (α1, α2, . . . , α3m).
I Relatie de ordine pe multimea triangularilor lui P: ordinealexicografica pentru vectorii unghiurilor. Fie T si T ′ doua triangulariale lui P. Atunci A(T ) > A(T ′) daca ∃i astfel ca αj = α′
j , ∀1 ≤ j < isi αi > α′
i .
I Triangulare unghiular optima: T astfel ca A(T ) ≥ A(T ′), pentruorice triangulare T ′.
I Exemplu: Cazul unui patrulater convex.
Triangulari 15 / 17
Triangulari unghiular optime
Muchii ilegale, triangulari legale
I Fixata: o multime de puncte P.
I Conceptul de muchie ilegala. Fie A,B,C ,D ∈ P fixate astfel caABCD sa fie un patrulater convex; fie TAC , TBD triangularile date dediagonalele AC , respectiv BD. Muchia AC este ilegala daca
minA(TAC ) < minA(TBD).
I Concluzie: Muchia AC este ilegala daca, printr-un flip (ınlocuirea eicu BD), cel mai mic unghi poate fi marit (local).
I Concluzie (reformulare): Fie T o triangulare cu o muchie ilegala e,fie T ′ triangularea obtinuta din T prin flip-ul muchiei e. AtunciA(T ′) > A(T ).
I Criteriu geometric pentru a testa daca o muchie este legala.
Triangulari 16 / 17
Triangulari unghiular optime
Muchii ilegale, triangulari legale
I Fixata: o multime de puncte P.
I Conceptul de muchie ilegala. Fie A,B,C ,D ∈ P fixate astfel caABCD sa fie un patrulater convex; fie TAC , TBD triangularile date dediagonalele AC , respectiv BD. Muchia AC este ilegala daca
minA(TAC ) < minA(TBD).
I Concluzie: Muchia AC este ilegala daca, printr-un flip (ınlocuirea eicu BD), cel mai mic unghi poate fi marit (local).
I Concluzie (reformulare): Fie T o triangulare cu o muchie ilegala e,fie T ′ triangularea obtinuta din T prin flip-ul muchiei e. AtunciA(T ′) > A(T ).
I Criteriu geometric pentru a testa daca o muchie este legala.
Triangulari 16 / 17
Triangulari unghiular optime
Muchii ilegale, triangulari legale
I Fixata: o multime de puncte P.
I Conceptul de muchie ilegala. Fie A,B,C ,D ∈ P fixate astfel caABCD sa fie un patrulater convex; fie TAC , TBD triangularile date dediagonalele AC , respectiv BD. Muchia AC este ilegala daca
minA(TAC ) < minA(TBD).
I Concluzie: Muchia AC este ilegala daca, printr-un flip (ınlocuirea eicu BD), cel mai mic unghi poate fi marit (local).
I Concluzie (reformulare): Fie T o triangulare cu o muchie ilegala e,fie T ′ triangularea obtinuta din T prin flip-ul muchiei e. AtunciA(T ′) > A(T ).
I Criteriu geometric pentru a testa daca o muchie este legala.
Triangulari 16 / 17
Triangulari unghiular optime
Muchii ilegale, triangulari legale
I Fixata: o multime de puncte P.
I Conceptul de muchie ilegala. Fie A,B,C ,D ∈ P fixate astfel caABCD sa fie un patrulater convex; fie TAC , TBD triangularile date dediagonalele AC , respectiv BD. Muchia AC este ilegala daca
minA(TAC ) < minA(TBD).
I Concluzie: Muchia AC este ilegala daca, printr-un flip (ınlocuirea eicu BD), cel mai mic unghi poate fi marit (local).
I Concluzie (reformulare): Fie T o triangulare cu o muchie ilegala e,fie T ′ triangularea obtinuta din T prin flip-ul muchiei e. AtunciA(T ′) > A(T ).
I Criteriu geometric pentru a testa daca o muchie este legala.
Triangulari 16 / 17
Triangulari unghiular optime
Muchii ilegale, triangulari legale
I Fixata: o multime de puncte P.
I Conceptul de muchie ilegala. Fie A,B,C ,D ∈ P fixate astfel caABCD sa fie un patrulater convex; fie TAC , TBD triangularile date dediagonalele AC , respectiv BD. Muchia AC este ilegala daca
minA(TAC ) < minA(TBD).
I Concluzie: Muchia AC este ilegala daca, printr-un flip (ınlocuirea eicu BD), cel mai mic unghi poate fi marit (local).
I Concluzie (reformulare): Fie T o triangulare cu o muchie ilegala e,fie T ′ triangularea obtinuta din T prin flip-ul muchiei e. AtunciA(T ′) > A(T ).
I Criteriu geometric pentru a testa daca o muchie este legala.
Triangulari 16 / 17
Triangulari unghiular optime
Triangulari unghiular optime vs. triangulari legale
I Triangulare legala: nu are muchii ilegale.
I O triangulare legala poate fi determinata pornind de la o triangularearbitrara.
I Propozitie. Fie P o multime de puncte din plan.
(i) Orice triangulare unghiular optima este legala.(ii) Daca P este ın pozitie generala (oricare patru puncte nu sunt
conciclice), atunci exista o unica triangulare legala, iar aceasta esteunghiular optima.
I Teorema. Fie P o multime de n puncte din plan, ın pozitie generala.Triangularea unghiular optima poate fi construita, folosind unalgoritm incremental randomizat, ın timp mediu O(n log n), folosindO(n) memorie medie.
Triangulari 17 / 17
Triangulari unghiular optime
Triangulari unghiular optime vs. triangulari legale
I Triangulare legala: nu are muchii ilegale.
I O triangulare legala poate fi determinata pornind de la o triangularearbitrara.
I Propozitie. Fie P o multime de puncte din plan.
(i) Orice triangulare unghiular optima este legala.(ii) Daca P este ın pozitie generala (oricare patru puncte nu sunt
conciclice), atunci exista o unica triangulare legala, iar aceasta esteunghiular optima.
I Teorema. Fie P o multime de n puncte din plan, ın pozitie generala.Triangularea unghiular optima poate fi construita, folosind unalgoritm incremental randomizat, ın timp mediu O(n log n), folosindO(n) memorie medie.
Triangulari 17 / 17
Triangulari unghiular optime
Triangulari unghiular optime vs. triangulari legale
I Triangulare legala: nu are muchii ilegale.
I O triangulare legala poate fi determinata pornind de la o triangularearbitrara.
I Propozitie. Fie P o multime de puncte din plan.
(i) Orice triangulare unghiular optima este legala.(ii) Daca P este ın pozitie generala (oricare patru puncte nu sunt
conciclice), atunci exista o unica triangulare legala, iar aceasta esteunghiular optima.
I Teorema. Fie P o multime de n puncte din plan, ın pozitie generala.Triangularea unghiular optima poate fi construita, folosind unalgoritm incremental randomizat, ın timp mediu O(n log n), folosindO(n) memorie medie.
Triangulari 17 / 17
Triangulari unghiular optime
Triangulari unghiular optime vs. triangulari legale
I Triangulare legala: nu are muchii ilegale.
I O triangulare legala poate fi determinata pornind de la o triangularearbitrara.
I Propozitie. Fie P o multime de puncte din plan.
(i) Orice triangulare unghiular optima este legala.(ii) Daca P este ın pozitie generala (oricare patru puncte nu sunt
conciclice), atunci exista o unica triangulare legala, iar aceasta esteunghiular optima.
I Teorema. Fie P o multime de n puncte din plan, ın pozitie generala.Triangularea unghiular optima poate fi construita, folosind unalgoritm incremental randomizat, ın timp mediu O(n log n), folosindO(n) memorie medie.
Triangulari 17 / 17