Note de curs, clasele 9-12, 30 ianuarie 2014

From Algopedia
Jump to navigationJump to search

Probleme cu puncte, dreptunghiuri și segmente

Aceste probleme sunt unificate mai mult prin enunț și mai puțin prin rezolvare, dar merită să le enumerăm împreună.

1D: Lungimea reuniunii a n segmente

Enunț: Se dau n segmente pe axa Ox. Să se afle lungimea reuniunii lor.

Există diverse metode de rezolvare în O(n log n).

  • Sortăm cele 2 * n capete de segment, apoi le parcurgem, ținând evidența numărului de segmente suprapuse (incrementăm când întâlnim capătul stâng al unui segment, decrementăm la capătul drept). De câte ori contorul este pozitiv, adăugăm lungimea intervalului curent.
  • Sortăm cele 2 * n coordonate, apoi le normalizăm la mulțimea { 1, ..., 2 * n }. Pentru fiecare element al mulțimii ținem un contor care indică numărul de segmente care acoperă acel interval. Pentru fiecare segment, incrementăm contorul pentru fiecare interval acoperit, în O(1), folosind șmenul lui Mars. La final, însumăm lungimile intervalelor acoperite de cel puțin un segment.

Dacă coordonatele sunt întregi și cuprinse între 0 și W, atunci există și un algoritm în O(n + W) care folosește memorie O(W). Tot folosind șmenul lui Mars, pentru fiecare segment [x, y] incrementăm valorile din vector pe poziții între x și y.

2D: Aria (sau perimetrul) reuniunii a n dreptunghiuri

Enunț: Se dau n dreptunghiuri în plan, cu laturile paralele cu axele. Să se afle aria (sau perimetrul) figurii rezultate.

  • prezentarea algoritmului de baleiere
  • reducerea la o problemă 1D
  • arbori de intervale
  • pentru arie, avem nevoie să calculăm, la fiecare moment în cursul baleierii, reuniunea segmentelor active pe linia de baleiere
  • pentru perimetru, avem nevoie doar de numărul de intervale (continue) acoperite de dreptunghiuri; vom calcula, separat, perimetrul pe segmente verticale și pe segmente orizontale
  • așadar, ce stocăm în fiecare nod al arborelui?

Complexitatea rezultată este O(n log n).

Aici este un moment bun să precizăm că există trei tipuri de arbori care stochează intervale, cu denumiri folosite neconsecvent. Noi vom folosi următoarele notații:

  1. arbore de segmente: un arbore static (nu admite inserări sau ștergeri), asemănător cu un heap peste cele 2 * n capete de segmente;
  2. arbore de intervale: un arbore dinamic, asemănător cu un heap peste mulțimea [xmin, xmax];
  3. arbore echilibrat de intervale: un arbore echilibrat (roșu-negru sau de altă natură), augmentat cu informații despre segmente în fiecare nod;

1D: Numărul maxim de segmente suprapuse

Enunț: Se dau n segmente închise pe axa Ox. Să se afle numărul maxim de segmente suprapuse.

Problema 1D anterioară (lungimea reuniunii) se adaptează imediat pentru această problemă.

2D: Numărul maxim de dreptunghiuri suprapuse

Enunț: Se dau n dreptunghiuri închise în plan, cu laturile paralele cu axele. Să se afle numărul maxim de dreptunghiuri suprapuse.

Algoritmul de baleiere de la problema anterioară se adaptează imediat pentru această problemă.

1D: Numărul de segmente intersectate de un punct (stabbing query)

Enunț: Se dau n segmente închise pe axa Ox și m puncte pe axa Ox. Pentru fiecare punct, să se spună în câte segmente este el inclus.

Această problemă este de tipul preprocesare + interogări. Întrucât nu avem de făcut ștergeri, ci doar inserări de segmente, putem folosi și un arbore de segmente. Complexitatea rezultată este O(n log n) pentru preprocesare și O(m log n) pentru a răspunde la interogări.

2D: Numărul de dreptunghiuri intersectate de un punct (stabbing query)

Enunț: Se dau n dreptunghiuri închise în plan, cu laturile paralele cu axele, și m puncte pe axa Ox. Pentru fiecare punct, să se spună în câte dreptunghiuri este el inclus.

Construim un arbore de intervale considerând proiecțiile segmentelor pe axa Ox. În fiecare nod din acest arbore, considerăm numai dreptunghiurile asociate cu acel nod (așadar cele care includ complet intervalul aferent nodului). În nod stocăm un arbore de intervale conținând numai acele dreptunghiuri.

Soluția este O(n log2 n) pentru preprocesare și O(m log2 n) pentru interogări.

1D: Numărul de puncte conținute de un segment (range query)

Enunț: Se dau n puncte închise pe axa Ox și m segmente pe axa Ox. Pentru fiecare segment, să se spună câte puncte conține.

Soluția evidentă este să sortăm punctele și să facem, pentru fiecare segment, două căutări binare. Aceasta ne oferă o complexitate O(n log n) pentru preprocesare și O(log n) per interogare. Dezavantajul este că nu se poate generaliza la spațiul 2D.

O altă soluție de aceeași complexitate se obține construind un arbore echilibrat și căutând, pentru fiecare segment [x, y], coordonatele x și y în arbore.

2D: Numărul de puncte conținute de un dreptunghi (range query)

Enunț: Se dau n puncte închise pe axa Ox și m dreptunghiuri cu laturi paralele cu axele. Pentru fiecare dreptunghi, să se spună câte puncte conține.

O primă soluție, în O(sqrt(n)) per query, construiește un arbore kD (prescurtare de la k-dimensional). În cazul nostru, k = 2. Divizăm binar spațiul prin tăieturi alternative, verticale și orizontale. Obținem astfel celule dreptunghiulare, posibil nemărginite. În frunze se află celule cu exact un punct.

  • Cum construim arborele kD în O(n log n)? Care este relația de recurență?
  • Cum răspundem la o interogare? Există următoarele cazuri:
    • celula v este o frunză
    • celula v este inclusă în dreptunghi
    • celula v este disjunctă de dreptunghi
    • alte cazuri
  • Care este complexitatea?
    • De interes sunt celulele care se intersectează cu dreptunghiul. Câte astfel de celule există?
    • Să considerăm o latură a dreptunghiului și două partiții succesive ale spațiului (una verticală, una orizontală)
    • Rezultă formula de recurență pentru numărul de intersecții: I(n) = 2 I(n/4) + 2, adică I(n) = O(sqrt(n))

O a doua soluție, considerabil mai dificil de implementat, recurge din nou la arbori de intervale pe două niveluri. Construim un arbore de intervale după coordonata X. În fiecare nod v stocăm arborele de intervale al tuturor punctelor conținute în subarborele lui v, ordonate de această dată după coordonata Y.

Complexitatea rezultată este O(n log2 n), iar memoria necesară O(n log n).