View source for Note de curs, clasele 9-12, 26 aprilie 2013

== Geometrie computațională -- recapitulare ==

* puncte, drepte
* pante, drepte paralele
* intersecția a două drepte
* dreapta determinată de două puncte

== Sweep line ==

* '''problemă:''' se dau ''n'' segmente în plan; există două care se intersectează?
* algoritm naiv: O(n<sup>2</sup>), 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 2''n'' 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

== Altă aplicație -- găsirea ''tuturor'' intersecțiilor a ''n'' segmente ==

* 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 2''n'' 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 3''n'' puncte: 2''n'' 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

== Altă aplicație: problema 1-d ==

* 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'']

==  Teme ==

* 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, <math>\lfloor n/3 \rfloor</math> 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 <math>\lfloor n/3 \rfloor</math> paznici sunt și necesari