Problema galeriei de arta

Triangularea poligoanelor

Mihai-Sorin Stupariu

Curs 9, Sem. I, 2011-2012

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Supravegherea unei galerii de arta

Camera din P poate supraveghea A, dar nu B.

����

rJJJJJJJ

P

rA

r B

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Formalizare

I O galerie de arta poate fi interpretata (ın contextul acesteiprobleme) ca un poligon simplu P (adica un poligon faraautointersectii) avand n varfuri.

I O camera video (vizibilitate 3600) poate fi identificata cu unpunct din interiorul lui P; ea poate supraveghea acele punctecu care poate fi unita printr-un segment inclus ın interiorulpoligonului.

I Problema galeriei de arta: cate camere video sunt necesarepentru a supraveghea o galerie de arta si unde trebuieamplasate acestea?

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Formalizare

I O galerie de arta poate fi interpretata (ın contextul acesteiprobleme) ca un poligon simplu P (adica un poligon faraautointersectii) avand n varfuri.

I O camera video (vizibilitate 3600) poate fi identificata cu unpunct din interiorul lui P; ea poate supraveghea acele punctecu care poate fi unita printr-un segment inclus ın interiorulpoligonului.

I Problema galeriei de arta: cate camere video sunt necesarepentru a supraveghea o galerie de arta si unde trebuieamplasate acestea?

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Formalizare

I O galerie de arta poate fi interpretata (ın contextul acesteiprobleme) ca un poligon simplu P (adica un poligon faraautointersectii) avand n varfuri.

I O camera video (vizibilitate 3600) poate fi identificata cu unpunct din interiorul lui P; ea poate supraveghea acele punctecu care poate fi unita printr-un segment inclus ın interiorulpoligonului.

I Problema galeriei de arta: cate camere video sunt necesarepentru a supraveghea o galerie de arta si unde trebuieamplasate acestea?

Mihai-Sorin Stupariu 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 catren).

I Pentru a supraveghea un spatiu avand forma unui poligonconvex, este suficienta o singura camera.

I Numarul de camere depinde si de forma poligonului: cu catforma este mai ”complexa”, cu atat numarul de camere va fimai mare.

I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).

Mihai-Sorin Stupariu 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 catren).

I Pentru a supraveghea un spatiu avand forma unui poligonconvex, este suficienta o singura camera.

I Numarul de camere depinde si de forma poligonului: cu catforma este mai ”complexa”, cu atat numarul de camere va fimai mare.

I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).

Mihai-Sorin Stupariu 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 catren).

I Pentru a supraveghea un spatiu avand forma unui poligonconvex, este suficienta o singura camera.

I Numarul de camere depinde si de forma poligonului: cu catforma este mai ”complexa”, cu atat numarul de camere va fimai mare.

I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).

Mihai-Sorin Stupariu 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 catren).

I Pentru a supraveghea un spatiu avand forma unui poligonconvex, este suficienta o singura camera.

I Numarul de camere depinde si de forma poligonului: cu catforma este mai ”complexa”, cu atat numarul de camere va fimai mare.

I Principiu: Poligonul considerat: descompus ın triunghiuri(triangulare).

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Definitie formala

I Fie P un poligon plan.

I (i) O diagonala a lui P este un segment ce uneste douavarfuri ale acestuia 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.

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Definitie formala

I Fie P un poligon plan.

I (i) O diagonala a lui P este un segment ce uneste douavarfuri ale acestuia 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.

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Definitie formala

I Fie P un poligon plan.

I (i) O diagonala a lui P este un segment ce uneste douavarfuri ale acestuia 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.

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Rezultate

I Lema. Orice poligon simplu admite o diagonala.

I Teorema. Orice poligon simplu admite o triangulare. Oricetriangulare a unui poligon cu n varfuri contine exact n − 2triunghiuri.

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Rezultate

I Lema. Orice poligon simplu admite o diagonala.

I Teorema. Orice poligon simplu admite o triangulare. Oricetriangulare a unui poligon cu n varfuri contine exact n − 2triunghiuri.

Mihai-Sorin Stupariu 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:fiecarui varf ıi corepunde o culoare dintr-un set de 3 culori sipentru fiecare triunghi, cele 3 varfuri au culori distincte.

I Observatie. Daca P este simplu, o astfel de colorare exista,deoarece graful asociat perechii (P, TP) este arbore.

Mihai-Sorin Stupariu 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:fiecarui varf ıi corepunde o culoare dintr-un set de 3 culori sipentru fiecare triunghi, cele 3 varfuri au culori distincte.

I Observatie. Daca P este simplu, o astfel de colorare exista,deoarece graful asociat perechii (P, TP) este arbore.

Mihai-Sorin Stupariu 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:fiecarui varf ıi corepunde o culoare dintr-un set de 3 culori sipentru fiecare triunghi, cele 3 varfuri au culori distincte.

I Observatie. Daca P este simplu, o astfel de colorare exista,deoarece graful asociat perechii (P, TP) este arbore.

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

Teorema galeriei de arta

I Teorema. [Chvatal, 1975; Fisk, 1978] Pentru un poligon cu n

varfuri,[n

3

]camere sunt uneori necesare si ıntotdeauna

suficiente pentru ca fiecare punct al poligonului sa fie vizibildin cel putin una din camere.

Mihai-Sorin Stupariu Triangularea poligoanelor

Problema galeriei de arta

C

at de

Mihai-Sorin Stupariu Triangularea poligoanelor