Note de curs, clasele 9-12, 7 noiembrie 2013

Am făcut geometrie computațională cu toate clasele împreună.

Recapitulare

• ecuația dreptei: ax + by + c = 0
  • forma cu pantă: y = mx + y0
  • dreapta care trece prin două puncte (x1, y1) și (x2, y2)
• date fiind două drepte, ax + by + c = 0 și dx + ey + f = 0,
  • dreptele paralele au aceeași pantă: ae = bd
  • dreptele perpendiculare au produsul pantelor egal cu -1, adică ad + be = 0
    • demonstrație: calculează tg(α + 90°)) = - 1 / tg(α)
• distanța de la punctul (m, n) la dreaptă: d = (am + bn + c) / sqrt(a² + b²)
  • schiță de demonstrație: dacă(x0, y0) este piciorul perpendicularei din punct pe dreaptă, atunci (n-y0)a = (m - x0)b
• normalizarea dreptei prin împărțirea la sqrt(a² + b²)
• separarea planului: semnul punctului la înlocuirea în ecuația dreptei ne indică de care parte a dreptei este.

Dualitate

• definită pentru dreptele care nu trec prin origine
• definită pentru toate punctele în afara originii
• fiecărei drepte d: ax + by + 1 = 0 îi asociem punctul P*(a,b)
• fiecărui punct P(a,b) ≠ O îi asociem dreapta d*: ax + by + 1 = 0
• se observă că P este dincolo de origine față de dreaptă, iar OP* ⊥ d
  • așadar, putem construi ochiometric punctul dual, ducând perpendiculara pe dreaptă prin origine și prelungind-o dincolo de ea.
• intuitiv, dreptele depărtate de origine se dualizează în puncte apropiate și invers
• concret, distanța de la dreaptă la origine este 1 / sqrt(a² + b²), iar PO* = sqrt(a² + b²)
• spațiu primal, spațiu dual

Proprietăți ale dualității

• punctele distincte se dualizează în drepte distincte și invers
• dreptele care trec prin origine nu se pot dualiza, căci ecuațiile nu pot fi împărțite prin c
  • intuitiv, deoarece dreptele care trec prin origine sunt la distanță 0 de origine, ele s-ar dualiza în puncte aflate la infinit
• două drepte d1 și d2 care se intersectează într-un punct P se dualizează în două puncte P1* și P2* care determină o dreaptă d*, unde d* este exact duala lui P
  • demonstrație: fie d1: ax + by + 1 = 0 și d2: dx + ey + 1 = 0. Fie (p,q) punctul lor de intersecție, deci ap + bq = dp + eq = -1. În planul dual, dreapta care trece prin punctele (a,b) și (d,e) are ecuația (x-a)/(d-a) = (y - b)/(e - b), adică (x-a)(e-b) = (y-b)(d-a). Amplificăm ambele părți cu pq, apoi reducem observând că (a-d)p = (e - b)q. Rezultă că ecuația lui d* este px + qy + 1 = 0, exact duala lui p.
• similar, două puncte care determină o dreaptă se dualizează în două drepte care se taie exact în punctul dual al dreptei
• generalizare: n puncte coliniare se generalizează într-un fascicul de drepte care se intersectează în punctul dual al dreptei (și invers)
  • demonstrație: scriem ecuația dreptelor duale și verificăm trivial că punctul dual este pe toate aceste drepte
• două drepte paralele se dualizează în două puncte coliniare cu originea (vizual)
• n drepte paralele se dualizează în n puncte coliniare
  • la fel ca și un fascicul de drepte, doar că punctul de intersecție este la infinit
• două drepte perpendiculare se dualizează în două puncte care, împreună cu originea, formează un triunghi dreptunghic
• un segment se dualizează în două unghiuri opuse la vârf
  • demonstrație: pentru a dualiza segmentul, dualizăm toate punctele de pe segment, obținând două fascicule de semidrepte opuse la vârf.
• conservarea orientării: P și O sunt de aceeași parte a lui d dacă și numai dacă Dual(d) și O sunt de aceeași parte a lui Dual(P)
  • demonstrație: considerăm câte o dreaptă paralelă cu d și vedem cum se dualizează toate punctele de pe ea.

Aplicații

• dându-se n drepte și un punct P(x,y), ce drepte sunt vizibile din P?
• O(n²) naiv
• Prin dualizare nu obținem ceva mult mai simplu. Ar trebui să găsim punctele cele mai „apropiate” de o dreaptă (definiție de altfel cam ambiguă)
• soluție: translatăm sistemul cu (-x, -y) astfel încât P să devină originea
• cum translatăm o dreaptă d: ax + by + c = 0 spre stânga cu (xt, yt)?
  • panta rămâne neschimbată; noua intercepție pe y va fi -(a/b)xt - c/b - yt
  • de aici rezultă noua ecuație d': ax + by + (axt + byt + c) = 0
• după dualizare, rezolvăm înfășurătoarea convexă
• demonstrație de corectitudine: cu conservarea orientării

diagrame Voronoi

• definiție, exemplu
• algoritm naiv: pentru fiecare punct, calculăm celula Voronoi pornind cu întregul dreptunghi, apoi retezând porțiuni de-a lungul mediatoarelor: O(n^{3), complicat}
• mai bine: pentru fiecare punct, considerăm mediatoarele și laturile dreptunghiului; apoi rezolvăm problema vizibilității
• complexitate O(n² log n) dacă facem înfășurătoarea convexă prin Graham scan
• până aici, știm doar dreptele care formează poligonul; dar, fiindcă le primim ordonate trigonometric, putem calcula și vârfurile poligonului: Pi = di ∩ di - 1.
• dacă folosim în loc algoritmul gift wrapping (Jarvis march), obținem O(n²)
  • demonstrație: suma punctelor de pe toate înfășurătoarele convexe va fi 2 * numărul de muchii din diagrama Voronoi, care este maxim 3n - 6
  • demonstrație: formula lui Euler este v + f - e = 2. Pentru o diagramă Voronoi cu un vârf adăugat la infinit, f = n + 1. Fiecare vârf are grad cel puțin 3, iar suma gradelor vârfurilor este 2e. Așadar, 2e >= 3(v + 1) ⇒ 2e >= 3(2 + e - n) = 6 + 3e - 3n ⇒ e <= 3n - 6
• divide et impera O(n log n), greu
• Fortune O(n log n) cu sweep “line”, greu