Clasele 11-12 lecția 3 - 1 oct 2014

From Algopedia
Revision as of 23:21, 14 October 2014 by Cata (talk | contribs)

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

Geometrie computațională, continuare

Șublerul rotitor (engl. rotating calipers)

În lecția trecută am folosit metoda șublerului rotitor pentru a afla diametrul unui poligon convex în O(n). Iată alte probleme rezolvabile cu aceeași metodă:

Distanța minimă între două poligoane convexe

Lățimea unui poligon convex

Lățimea unui poligon convex este distanța cea mai mică între două drepte suport paralele. Desigur, algoritmul este similar cu cel pentru aflarea diametrului, doar că extragem minimul în loc de maxim.

Distanța minimă între două poligoane convexe

Dându-se două poligoane convexe disjuncte, trebuie să găsim câte un punct pe conturul fiecăruia astfel încât distanța să fie minimă. Există trei situații, ilustrate la dreapta.

Există două lucruri speciale față de problema diametrului:

  1. Distanța minimă se poate obține între un vârf al unui poligon și un punct de pe o latură a celuilalt poligon. Cazul al treilea, în care ambele puncte sunt pe latură, poate fi redus la cazul al doilea prin translatarea segmentului de legătură până la suprapunerea peste un vârf.
  2. Cele două drepte suport rămân paralele, dar se înfășoară pe poligoane diferite.

Putem rezolva „băbește” problema calculând, de fiecare dată, unghiul minim cu care putem roti simultan ambele drepte până când una dintre ele se suprapune peste o nouă latură a poligonului. Provocarea este să găsim perechile de puncte antipodale fără a face împărțiri sau alte operații mai scumpe.

Dreptunghiul de arie minimă care conține un poligon convex

Dându-se un poligon convex, trebuie să găsim dreptunghiul de arie minimă (nu neapărat paralel cu axele) care conține poligonul. Problema se simplifică mult odată ce demonstrăm că dreptunghiul se suprapune neapărat peste una dintre laturile poligonului (de ce?). Chiar și așa, o căutare naivă de minime și maxime relativ la o direcție dată duce la un algoritm în O(n2).

Putem obține un algoritm liniar folosind două perechi de drepte suport care formează un dreptunghi. Apoi, rotim dreptunghiul până când oricare dintre laturi se suprapune peste o latură a poligonului.

Ca de obicei, provocarea este să scriem algoritmul folosind doar înmulțiri.

Găsim împreună algoritmul și scriem pseudocodul.

Pentru multe alte probleme rezolvabile cu șublerul rotitor, vedeți [această pagină].

Înfășurătoarea convexă (engl. convex hull)

Înfășurătoarea convexă a unui set de n puncte este cel mai mic poligon convex care conține acele puncte (inclusiv pe contur). Este ușor de demonstrat că toate vârfurile poligonului sunt puncte din set (cum?).

În această secțiune, vom nota cu h numărul de puncte de pe înfășurătoare.

Algoritmul naiv

Pentru fiecare pereche de puncte, calculăm ecuația dreptei și testăm dacă toate celelalte puncte sunt de aceeași parte a dreptei. Dacă da, atunci perechea de puncte formează o latură a înfășurătorii convexe.

Complexitate: O(n3).

Algoritmul mai puțin naiv

  • Pornim dintr-un punct P0 care aparține garantat înfășurătorii, de exemplu punctul cu y minim.
  • Pentru fiecare punct Q ≠ P0, verificăm dacă toate celelalte n - 2 puncte se află la stânga dreptei orientate P0Q. Acest punct există și este unic. Fie acesta P1.
  • Repetăm procedura pentru a găsi punctele P2, ..., Ph - 1, Ph = P0.

Complexitate: O(n2h).

Algoritmul înfășurarea cadoului (numit și Marșul lui Jarvis)

Înfășurarea cadoului
  • Aflăm întâi jumătatea dreaptă a înfășurătorii.
    • Pornim dintr-un punct P0 care aparține garantat înfășurătorii, de exemplu punctul cu y minim.
    • Următorul punct de pe înfășurătoare P1 este cel care formează unghiul polar minim raportat la P0.
    • Următorul punct de pe înfășurătoare P2 este cel care formează unghiul polar minim raportat la P1.
    • Continuăm până ajungem la punctul cu y maxim, Pk
  • Pentru a afla jumătatea stângă, repetăm aceiași pași, dar căutăm puncte cu unghi polar minim în sensul negativ al axei x.

De ce împărțim algoritmul în două jumătăți? În prima jumătate, știm că putem examina doar puncte cu y crescător. Atunci unghiurile minime formate vor fi neapărat între 0° și 180° și putem compara unghiuri polare cu doar două înmulțiri. Punctul P3 formează un unghi polar mai mic decât P2 raportat la P1 dacă

(x_{3}-x_{1})(y_{2}-y_{1})-(x_{2}-x_{1})(y_{3}-y_{1})>0

Observații:

  • Dacă vi se pare că formula de sus seamănă cu testul de orientare, nu vă înșelați. P3 formează un unghi polar mai mic decât P2 dacă triunghiul P1P2P3 are orientare orară.
  • În caz de egalitate, punctele sunt coliniare și selectăm punctul cel mai depărtat de P1.

Complexitate: O(nh).

Algoritmul Graham's scan

Graham's scan. Punctul P6 cauzează eliminarea din stivă a punctelor P3, P4 și P5
  • Pornim dintr-un punct P0 care aparține garantat înfășurătorii, de exemplu punctul cu y minim.
  • Fie P1', P2, ..., Pn - 1 celelalte puncte, sortate polar în raport cu P0.
  • Inserăm într-o stivă punctele P0 și P1.
  • Pentru fiecare punct P2 ... Pn - 1,
    • cât timp unghiul format de ultimele două puncte din stivă și Pi depășește 180°,
      • elimină vârful stivei.
    • adaugă Pi în stivă.

La final, stiva conține punctele de pe înfășurătoare, în ordine trigonometrică.

Complexitate: O(n\log n) pentru sortare, O(n) pentru algoritmul în sine.

Demonstrația complexității (stiva este ordonată polar).

Putem demonstra că O(n\log n) este optim asimptotic, arătând că problema sortării se poate reduce la o problemă de înfășurătoare convexă. Presupunem că dorim să sortăm un vector de numere (a1, a2, ... , an) și că există un algoritm pentru aflarea înfășurătoarei convexe în o(n\log n), de exemplu în O(n). Atunci apelăm algoritmul cu n puncte de coordonate (a1, a12), (a2, a22), ..., (an, an2). Aceste puncte aparțin de o parabolă, deci clar formează o mulțime convexă. Algoritmul de înfășurătoare va rula în O(n) și ni le va da în ordine sortată, ceea ce este absurd.

Temă