Algoritm de baleiere

Animație a algoritmului lui Fortune^⁠(d), o tehnică a dreptei de baleiere pentru construirea diagramelor Voronoi^⁠(d)

În geometria algoritmică^⁠(d) un algoritm de baleiere sau algoritm de baleiere a planului este un exemplu de algoritm care utilizează o dreaptă de baleiere pentru a rezolva diverse probleme din spațiul euclidian. Este una dintre tehnicile cheie în geometria algoritmică.

Ideea algoritmilor de acest tip este că o dreaptă (adesea o dreaptă verticală) mătură planul, oprindu-se în anumite puncte. Operațiile geometrice sunt limitate la obiectele geometrice care fie se intersectează cu dreapta de baleiere, fie se află în imediata ei apropiere ori de câte ori aceasta se oprește, iar soluția completă este disponibilă după ce dreapta a trecut peste toate obiectele.

Istoric

Această abordare poate fi găsită la algoritmii cu dreaptă de scanare^⁠(d) pentru generarea imaginilor în grafica digitală, urmată de exploatarea acestei abordări în vechii algoritmi de proiectare a circuitelor integrate, în care descrierea geometrică a unui circuit integrat a fost împărțită în benzi paralele, deoarece întreaga descriere nu a putut încăpea în memorie.

Aplicații

Aplicarea acestei abordări a condus la o descoperire în complexitatea algoritmilor geometrici când Michael Ian Shamos și Dan Hoey au prezentat algoritmi pentru intersecția^⁠(d) segmentelor de dreaptă în plan și au descris modul în care o combinație între scanări și structuri eficiente de date (arbore binar de căutare autoechilibrat^⁠(d)) face posibilă detectarea intersecțiilor între N segmente din plan cu complexitatea în timp O(N log N). Algoritmul Bentley–Ottmann înrudit folosește tehnica dreptei de baleiere pentru a găsi toate cele K intersecții între oricare N segmente din plan, cu complexitatea în timp O((N + K) log N), respectiv cea în spațiu O(N).