Geometrie computațională

Obiectivul principal al cercetării în geometria computațională combinatorie este de a dezvolta algoritmi și structuri de date eficiente pentru rezolvarea problemelor enunțate în termeni de obiecte geometrice de bază: puncte, segmente de dreaptă, poligoane, poliedre, etc.

Câteva dintre aceste probleme par atât de simple încât nu au fost considerate probleme până la apariția calculatoarelor. Luați în considerare, de exemplu, problema Perechea cea mai apropiată:

• Date n puncte din plan, găsiți-le pe cele două care au cea mai mică distanță una față de cealaltă.

Se pot calcula distanțele dintre toate perechile de puncte, dintre care există n(n-1)/2, apoi se poate alege perechea cu cea mai mică distanță. Acest algoritm de forță brută durează O(n2); adică timpul său de execuție este proporțional cu pătratul numărului de puncte. Un rezultat clasic în geometria computațională a fost formularea unui algoritm care durează O(n log n). Au fost descoperiți, de asemenea, algoritmi aleatori care durează O(n) timp așteptat, precum și un algoritm determinist care durează O(n log log n).

Clase de problemeEdit

Problemele de bază din geometria computațională pot fi clasificate în diferite moduri, în funcție de diverse criterii. Se pot distinge următoarele clase generale.

Probleme staticeEdit

În problemele din această categorie, se dă o anumită intrare și trebuie construită sau găsită ieșirea corespunzătoare. Câteva probleme fundamentale de acest tip sunt:

• Cocă convexă: Dat fiind un set de puncte, găsiți cel mai mic poliedru/poligon convex care conține toate punctele.
• Intersecția segmentelor de dreaptă: Găsiți intersecțiile dintre un set dat de segmente de dreaptă.
• Triangulația Delaunay
• Diagrama Voronoi: Dat un set de puncte, împărțiți spațiul în funcție de punctele care sunt cele mai apropiate de punctele date.
• Programare liniară
• Cea mai apropiată pereche de puncte: Având în vedere un set de puncte, găsiți cele două puncte aflate la cea mai mică distanță unul față de celălalt.
• Cea mai îndepărtată pereche de puncte
• Cel mai mare cerc gol: Fiind dat un set de puncte, găsiți cel mai mare cerc cu centrul în interiorul corpului convex al acestora și care nu înconjoară niciunul dintre ele.
• Cea mai scurtă cale euclidiană: Conectați două puncte dintr-un spațiu euclidian (cu obstacole poliedrice) printr-un drum cel mai scurt.
• Triangularea poligonală: Dat un poligon, împărțiți interiorul acestuia în triunghiuri
• Generarea de rețele
• Operații booleene pe poligoane

Complexitatea de calcul pentru această clasă de probleme este estimată prin timpul și spațiul (memoria calculatorului) necesare pentru a rezolva o anumită instanță a problemei.

Probleme de interogare geometricăEdit

În problemele de interogare geometrică, cunoscute în mod obișnuit sub numele de probleme de căutare geometrică, datele de intrare constau din două părți: partea de spațiu de căutare și partea de interogare, care variază în funcție de instanțele problemei. Spațiul de căutare trebuie, de obicei, să fie preprocesat, astfel încât să se poată răspunde eficient la mai multe interogări.

Câteva probleme fundamentale de interogare geometrică sunt:

• Căutarea în interval: Preprocesarea unui set de puncte, pentru a număra eficient numărul de puncte din interiorul unei regiuni de interogare.
• Localizarea punctelor: Având în vedere o partiționare a spațiului în celule, se produce o structură de date care să indice în mod eficient în ce celulă se află un punct de interogare.
• Vecinul cel mai apropiat: Prelucrarea prealabilă a unui set de puncte, pentru a afla în mod eficient care punct este cel mai apropiat de un punct de interogare.
• Trasarea razelor: Dat fiind un set de obiecte în spațiu, produceți o structură de date care să spună în mod eficient ce obiect intersectează mai întâi o rază de interogare.

Dacă spațiul de căutare este fix, complexitatea de calcul pentru această clasă de probleme este de obicei estimată prin:

• timpul și spațiul necesar pentru a construi structura de date în care se va căuta
• timpul (și uneori un spațiu suplimentar) pentru a răspunde la interogări.

Pentru cazul în care se permite ca spațiul de căutare să varieze, vezi „Probleme dinamice”.

Probleme dinamiceEdit

O altă clasă importantă este cea a problemelor dinamice, în care scopul este de a găsi un algoritm eficient pentru găsirea unei soluții în mod repetat după fiecare modificare incrementală a datelor de intrare (adăugare sau ștergere de elemente geometrice de intrare). Algoritmii pentru probleme de acest tip implică, de obicei, structuri de date dinamice. Oricare dintre problemele geometrice de calcul poate fi transformată într-una dinamică, cu prețul creșterii timpului de procesare. De exemplu, problema de căutare a intervalului poate fi convertită în problema de căutare dinamică a intervalului, prevăzând adăugarea și/sau ștergerea punctelor. Problema coca convexă dinamică constă în urmărirea coca convexă, de exemplu, pentru setul de puncte care se schimbă în mod dinamic, și anume, în timp ce punctele de intrare sunt inserate sau șterse.

Complexitatea de calcul pentru această clasă de probleme este estimată prin:

• timpul și spațiul necesar pentru a construi structura de date în care se caută
• timpul și spațiul pentru a modifica structura de date căutată după o schimbare incrementală în spațiul de căutare
• timpul (și uneori un spațiu suplimentar) pentru a răspunde la o interogare.

VarianteEdit

Câteva probleme pot fi tratate ca aparținând oricăreia dintre aceste categorii, în funcție de context. De exemplu, considerați următoarea problemă.

• Punct în poligon: Decideți dacă un punct se află în interiorul sau în exteriorul unui poligon dat.

În multe aplicații această problemă este tratată ca una cu o singură lovitură, adică aparținând primei clase. De exemplu, în multe aplicații de grafică pe calculator, o problemă obișnuită este aceea de a afla ce zonă de pe ecran a fost apăsată de un pointer. Cu toate acestea, în unele aplicații, poligonul în cauză este invariabil, în timp ce punctul reprezintă o interogare. De exemplu, poligonul de intrare poate reprezenta granița unei țări, iar un punct este poziția unui avion, iar problema este de a determina dacă avionul a încălcat granița. În cele din urmă, în exemplul de grafică pe calculator menționat anterior, în aplicațiile CAD, datele de intrare în schimbare sunt adesea stocate în structuri de date dinamice, care pot fi exploatate pentru a accelera interogările de tip punct în poligon.

În unele contexte de probleme de interogare există așteptări rezonabile privind succesiunea interogărilor, care pot fi exploatate fie pentru structuri de date eficiente, fie pentru estimări mai stricte ale complexității de calcul. De exemplu, în unele cazuri, este important să se cunoască cel mai rău caz pentru timpul total pentru întreaga secvență de N interogări, mai degrabă decât pentru o singură interogare. A se vedea, de asemenea, „analiză amortizată”.

.