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

From Algopedia
Revision as of 09:32, 7 May 2013 by Cata (talk | contribs) (Altă aplicație: problema 1-d)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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
  • 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, \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