Note de curs, clasele 9-12, 26 aprilie 2013
From Algopedia
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(n2), 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
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 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
- dacă este începutul unui segment s:
- 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
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, 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 paznici sunt și necesari