Graham's Scan - Varianta Andrew — Acoperiri Convexe

01 Problema: Acoperirea Convexă

Se dă: o mulțime finită de puncte P ⊂ R². Acoperirea convexă conv(P) este cel mai mic poligon convex care conține P. Se cere: vârfurile ei, în sens trigonometric (CCW).

⚠️ O definiție corectă nu e încă un algoritm. Cele trei caracterizări echivalente ale acoperirii convexe — „cea mai mică mulțime convexă ⊇ P", „intersecția tuturor mulțimilor convexe ⊇ P" și „mulțimea tuturor combinațiilor convexe" — sunt toate corecte, dar descriptive, nu constructive: spun ce este acoperirea, nu cum se obține (ar cere verificarea unei infinități de mulțimi/combinații). Examenul cere un răspuns constructiv: vârfurile și ordinea în care se unesc. Verificarea fiecărei muchii orientate față de toate punctele dă răspunsul corect, dar în O(n³); sortarea e cea care deblochează parcurgerea în O(n log n).

Graham's Scan - Varianta Andrew: sortăm punctele lexicografic, apoi o parcurgere stânga→dreapta construiește marginea inferioară (L_i) și o parcurgere dreapta→stânga marginea superioară (L_s) — eliminând de fiecare dată cât timp ultimele trei puncte NU formează un viraj la stânga. O(n log n), dominat de sortare.

02 De reținut

Primitiva Testul de orientare

Δ(a,b,c) = (x_b−x_a)(y_c−y_a) − (y_b−y_a)(x_c−x_a) (determinantul 3×3)
Δ > 0 ⇒ viraj la stânga (CCW, sens trigonometric) ⇒ păstrăm
Δ < 0 ⇒ viraj la dreapta ⇒ eliminăm; Δ = 0 ⇒ coliniare ⇒ eliminăm și aici

Folosit la fiecare pas de aici.

Cifre Tabel de complexitate (de memorat)

Algoritm	Timp	Notă
Naiv (toate muchiile)	O(n³)	fiecare muchie orientată față de toate punctele
Graham / Andrew	O(n log n)	sortarea domină; parcurgerea O(n)
Jarvis march	O(n·h)	h = vârfuri de frontieră; fără sortare
Chan	O(n log h)	optim, output-sensitive (doar numele)

Anatomie Frontiera se descompune

Parcurgere CCW: marginea inferioară L_i (cel mai din stânga → cel mai din dreapta) apoi marginea superioară L_s (cel mai din dreapta → cel mai din stânga).
Cele două capete sunt comune — scoți ultimul element al fiecărui lanț la concatenare.
Aceeași regulă de eliminare pentru ambele; se schimbă doar sensul de parcurgere.

Context Dimensiuni & sortare

d=1: acoperirea = segment [min, max], găsit în O(n) — fără sortare.
d=2: poligon convex; d=3: poliedru convex.
Lexicografic = după x, la egalitate după y — varianta Andrew. Sortarea după unghi polar este varianta inițială a lui Graham, nu cea predată aici.

03 Algoritmii

O singură regulă de eliminare, două parcurgeri — plus companionul fără sortare cu care se compară exercițiile.

A Graham's Scan - Varianta Andrew (lanț monoton)

sortează lexicografic: după x, la egalitate după y   [O(n log n)]
L ← ∅                          # marginea inferioară, stânga → dreapta
pentru i = 1 .. n:
    cât timp |L| ≥ 2 și turn(L[-2], L[-1], p_i) NU e viraj la stânga:
        elimină L[-1]          # viraj la dreapta SAU coliniare
    adaugă p_i
U ← ∅  — aceeași parcurgere, dreapta → stânga   # marginea superioară
frontieră ← L[:-1] ++ U[:-1]   # capete comune, listate o singură dată

Eliminarea e un cât timp, nu un if — un singur punct nou poate șterge o întreagă cascadă de puncte vechi. După fiecare eliminare, re-testează față de noul vârf.

B Jarvis march (gift wrapping — companion)

start ← punctul cel mai din stânga  # sigur pe frontieră   [O(n)]
repetă:
    următorul vârf de frontieră ← candidatul cel mai la dreapta:
      parcurge toate punctele; păstrează S astfel încât orice alt
      punct să fie la stânga muchiei (curent → S)
până la revenirea în start          # O(n) per vârf de frontieră

O(n·h) — output-sensitive, fără sortare. Excelent când h e mic, degenerează la O(n²) când majoritatea punctelor sunt pe frontieră. Chan le combină pe cele două pentru O(n log h) — reține numele și limita, detaliile interne sunt în afara programei.

04 Simulator

Demonstrație reia traseul canonic — fiecare test de orientare, fiecare cascadă, cu jurnalul listei L construindu-se în format de examen. Exersează e modul examen: la fiecare test tu decizi dacă elimini sau adaugi și ești evaluat.

marginea inferioară L_i marginea superioară L_s candidatul curent eliminat culorile testului: stânga / dreapta / coliniare

05 Laborator — cazuri degenerate: serii coliniare, egalități la x și h față de n

Cele două forme-capcană clasice, plus cursa pe numărul de operații care decide Graham vs Jarvis.

A · Serii coliniare & x duplicat

Punctele coliniare interioare nu sunt vârfuri de frontieră — dispar la eliminări cu Δ = 0. Coordonatele x duplicate sunt ordonate după criteriul secundar y al sortării lexicografice.

B · Graham vs Jarvis — cursa pe numărul de operații

n = 12 puncte fixe; reglează câte stau pe frontieră. Parcurgerea lui Graham nu depășește niciodată 2n teste per lanț (dar plătește sortarea); Jarvis plătește ≈ h·(n−2).

06 Antrenament: demonstrații

Cele două răspunsuri „justificați": de ce parcurgerea e O(n) (amortizare — cifrele de mai jos sunt numărătorile reale din trasarea cu 12 puncte) și de ce eliminarea e sigură.

07 Capcane și greșeli frecvente

⚠️ „Nu e viraj la stânga" = viraj la dreapta SAU coliniare Ambele se elimină. Punctele coliniare interioare nu sunt vârfuri de frontieră — eliminările coliniare din exercițiile D1 (P6-P5-P2) și D2 (P2-P3-P4) sunt capcanele clasice.

⚠️ Eliminarea e un cât timp, nu un if Un singur punct nou poate declanșa o cascadă (P12 elimină trei deodată în trasarea cu 12 puncte). Re-verifică mereu noul vârf după fiecare eliminare.

⚠️ Ordinea povestită vs bucla strictă În exemplul cu 12 puncte, bucla strictă de eliminare scoate P3 ȘI P4 la pasul P5 (P2P3P5 e tot un viraj la dreapta). O trasare de mână pas cu pas amână adesea dispariția lui P3 până la tripletul coliniar P2-P3-P6. Aceeași frontieră finală — dar scrie versiunea mecanică la examen.

⚠️ Inferioară vs superioară — direcția Inferioară: stânga→dreapta. Superioară: dreapta→stânga. Dacă parcurgi marginea superioară stânga→dreapta, doar reconstruiești inferioara. Regula de eliminare e identică — se schimbă doar sensul de parcurgere.

⚠️ Nu dubla capetele Punctele cel mai din stânga și cel mai din dreapta aparțin ambelor lanțuri. La concatenare, scoate ultimul element al fiecărui lanț ca fiecare vârf să fie listat o singură dată.

⚠️ Lexicografic = după x, apoi y Nu după unghi polar (aceea e varianta inițială a lui Graham, nu Andrew). Egalitățile la x se rup după y — vezi P3 = (−4,0) înaintea lui P4 = (−4,2) în instanța cu 12 puncte.

⚠️ O(n log n) — iar sortarea e factorul dominant Parcurgerea singură e O(n) (amortizat). Răspunsul „O(n)" uită de sortare; „O(n²)" o confundă cu naivul / cazul cel mai defavorabil al lui Jarvis.

⚠️ Jarvis e O(n·h), nu O(n log n) Mai bun când h e mic, mai slab (→ O(n²)) când toate punctele sunt pe frontieră. Chan, O(n log h), e cel mai bun din ambele — pune-i la întrecere în laboratorul B.

⚠️ Convenția semnului la orientare + = stânga/CCW = păstrăm; − = dreapta = eliminăm. Cu semnul inversat construiești lanțul greșit — verifică pe un triplet pe care îl poți vedea.

08 Exerciții

D1–D4 sunt probleme complete de trasare / construcție; G1–G2 sunt de tip grilă. Testează-te întâi, apoi dezvăluie.

D1 Trasează ambele lanțuri 7 puncte · mod Exersează

P1=(1,1), P2=(2,7), P3=(3,6), P4=(4,5), P5=(7,7), P6=(9,7), P7=(11,1). Exersează marginea inferioară, apoi comută pe superioară — atenție la eliminarea coliniară.

Arată soluția canonică

Inferioară L_i — fiecare punct din mijloc se află deasupra segmentului P1→P7, deci fiecare sosire elimină predecesorul (Δ: −7, −7, −6, −12, −60): lista nu crește niciodată peste P1 Pₖ. L_i = P1, P7.

Superioară L_s (dreapta→stânga): se construiește la P7 P6 P5 P4; P3 elimină P4 (Δ −5); P2 elimină P3 (Δ −5) apoi P5 pe tripletul coliniar P6-P5-P2 (Δ = 0); P1 se adaugă. L_s = P7, P6, P2, P1.

Frontiera completă (CCW): P1, P7, P6, P2.

D2 Lungimea maximă a listei 9 puncte · Exersează + numeric

P1=(−3,2), P2=(−2,−1), P3=(−1,−1), P4=(1,−1), P5=(3,1), P6=(4,3), P7=(5,7), P8=(7,2), P9=(9,4). Exersează marginea inferioară, urmărind cât de lungă devine lista — apoi răspunde mai jos.

Arată raționamentul

P3 dispare devreme (P2-P3-P4 coliniare pe y = −1). Lista urcă apoi seria crescătoare P5-P6-P7 până la lungimea 6 = P1 P2 P4 P5 P6 P7 când se adaugă P7 — maximul. Imediat după, P8 declanșează o cascadă peste P7, P6, P5, iar lista nu mai crește peste 6. Marginea inferioară finală: P1, P2, P4, P8, P9.

D3 Testele de succesor Jarvis 5 puncte · Demonstrație + grilă

P1=(2,0), P2=(0,3), P3=(−4,0), P4=(4,2), P5=(5,1). Convenție: candidații în ordinea de intrare, primul devine pivotul S; fiecare P ulterior cu turn(M, S, P) = dreapta fură pivotul. Urmărește testele, apoi răspunde.

Arată răspunsul complet

Succesorul lui M = P3 (cel mai din stânga): init S = P1; P2, P4, P5 sunt toate la stânga razei P3→P1 (Δ: +18, +12, +6) — S nu se schimbă niciodată ⇒ succesor = P1.

Succesorul lui P1: init S = P2; Δ(P1,P2,P3) = +18 stânga; Δ(P1,P2,P4) = −10 dreapta ⇒ S := P4; Δ(P1,P4,P5) = −4 dreapta ⇒ S := P5 ⇒ succesor = P5. Parcurgerea CCW completă: P3, P1, P5, P4, P2.

Start de jos: min y = 0 este la egalitate între P3 și P1; criteriul obișnuit cel mai de jos, apoi cel mai din stânga alege tot P3 ⇒ testele sunt exact aceleași. (Un criteriu cel-mai-de-jos-apoi-cel-mai-din-dreapta ar porni în schimb din P1, cu un vârf mai departe pe parcurgere.)

D4 Construcția cazului cel mai defavorabil Jarvis construcție · 8 puncte

P1=(0,0) cel mai din stânga, P2=(8,6), P8=(8,−6) și cinci puncte P3..P7 strict în interiorul triunghiului P1-P2-P8, aranjate după unghi polar descrescător față de P1. Găsirea succesorului lui P1 testează atunci fiecare candidat — și fiecare test fură pivotul:

Arată raționamentul

Frontiera = exact 3 vârfuri {P1, P2, P8} — P3..P7 sunt strict în interiorul triunghiului. La găsirea succesorului lui P1: candidații apar în ordinea unghiului polar descrescător, deci fiecare test e un viraj la dreapta și pivotul se actualizează la fiecare pas (Δ: −6, −8, −12, −12, −8, −6), terminând la P8. Toate cele 7 puncte ne-din-stânga au fost examinate — parcurgerea în cazul cel mai defavorabil O(n·h) deși h = 3.

D5 Grilă G1 complexitate

D6 Grilă G2 asociază complexitățile

D7 Enunță & demonstrează — probabila întrebare „justificați" exercițiu de demonstrație

De ce este întregul algoritm O(n log n)? Spune argumentul de amortizare cu voce tare înainte de a dezvălui.

Arată răspunsul în trei rânduri

Sortare: sortarea lexicografică = O(n log n).

Parcurgerea e O(n) amortizat: fiecare punct este adăugat exact o dată și eliminat cel mult o dată (odată ieșit din L nu mai revine), deci operațiile pe listă ≤ 2n; fiecare test de orientare ori elimină, ori încheie bucla cât-timp, deci și testele ≤ 2n.

Total: O(n log n) + O(n) + O(n) = O(n log n) — sortarea domină. ∎

Repetă-l cu numărătorile reale din trasarea cu 12 puncte în antrenamentul de demonstrații, tabul (a).