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 navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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