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