Note de curs, clasele 9-12, 26 aprilie 2013

Geometrie computațională -- recapitulare

problemă: se dau n segmente în plan; există două care se intersectează?
algoritm naiv: O(n²), fiecare cu fiecare
idee de îmbunătățire: sortăm segmentele. Nu are sens să testăm un segment care deja s-a terminat cu altul care încă nu a început
parcurgem planul de la stânga la dreapta cu o linie de baleiere (sweep line) și facem opriri în 2n puncte de interes (capetele segmentelor).
pe parcurs, întreținem lista de segmente intersectate de linia de baleiere, ordonate de sus în jos
avem nevoie de o structură de valori sortate care să permită următoarele operații în O(log n):
- inserare
- ștergere
- predecesor
- succesor
putem folosi arbori de căutare echilibrați sau skip lists (nu le-am predat încă)
- scurt exemplu pentru ideea generală a arborilor echilibrați: rotația
în această structură, în loc de comparații pe numere folosim produse vectoriale ca să aflăm unde în listă trebuie inserat un nou segment
pentru fiecare din cele 2n puncte,
- dacă punctul este începutul unui segment s, inserează s în structura ordonată. Fie r predecesorul. Dacă există, verifică dacă r și s se intersectează. Idem pentru succesor.
- dacă punctul este sfârșitul unui segment s, șterge s din structura ordonată. Fie r și t predecesorul și succesorul. Dacă ambii există, verifică dacă r și t se intersectează.
complexitatea totală este O(n log n)
cazuri particulare:
- segmente verticale;
- intersecții de trei segmente în același punct

algoritmul anterior nu poate fi aplicat pentru găsirea tuturor intersecțiilor
- exemplu când algoritmul pierde intersecții
Bentley-Ottman au inventat o generalizare
pornim cu cele 2n puncte într-o coadă de priorități ordonată după coordonata x
cu timpul, coada de priorități va ține și intersecții viitoare ale segmentelor baleiate până acum
pentru fiecare punct din coadă,
- dacă este începutul unui segment s:
  - inserează-l în lista ordonată, fie r predecesorul și t succesorul
  - șterge r x t din coadă dacă exista
  - inserează r x s și s x t în coadă dacă este cazul
- dacă este sfârșitul unui segment s:
  - șterge-l din lista ordonată, fie r predecesorul și t succesorul
  - inserează r x t în coadă dacă este cazul
- dacă este intersecția a două segmente s și t:
  - schimbă ordinea lui s și t în lista ordonată
  - șterge r x s și t x u din coadă dacă existau
  - inserează r x t și s x u din coadă dacă este cazul
motivul pentru care ștergem intersecții din coadă este ca memoria necesară să rămână O(n)
la fiecare moment, în coadă avem maxim 3n puncte: 2n capete de segmente și n intersecții de segmente consecutive în lista ordonată
complexitate: O((n + k) log n), unde k este numărul de intersecții
îmbunătățit de Balaban O(n log n + k), dar considerabil mai greu

se dau n intervale pe axa Ox; există două care se intersectează?
cu sweep line, O(n log n)
sigur, se poate face și prin sortarea punctelor și menținerea unui contor de intervale deschise
discuție despre de ce O(n log n) este optim
- problema elementelor distincte: dându-se n numere, există două egale?
- aceasta este O(n log n) demonstrabil, căci un „certificat” (o garanție a unui răspuns) trebuie să indice o ordonare a elementelor
- problema elementelor distincte se reduce la problema intervalelor 1-d
- înlocuim fiecare element x prin intervalul [x, x]

intersecția a două poligoane convexe în O(n)
cum testăm dacă un poligon este simplu (adică nu se autointersectează)
Teorema galeriei de artă: în orice galerie de forma unui poligon cu n laturi, $\lfloor n/3\rfloor$ paznici sunt suficienți ca să vadă tot interiorul poligonului (paznicii sunt statici, dar văd 360° în jur).
Găsiți un exemplu pentru care $\lfloor n/3\rfloor$ paznici sunt și necesari