Triangulația Delaunay

Triangulația Delaunay este o triangulație pentru un set dat de puncte S pe un plan, în care pentru orice triunghi toate punctele din S , cu excepția punctelor care sunt vârfurile sale, se află în afara cercului descris în jurul triunghiului. Notat DT( S ) . Descris pentru prima dată în 1934 de către matematicianul sovietic Boris Delaunay .

Proprietăți

Triangulația Delaunay corespunde unu-la-unu diagramei Voronoi pentru același set de puncte.
Ca un corolar: dacă nu există patru puncte pe același cerc, triangulația Delaunay este unică.
Triunghiularea Delaunay maximizează unghiul minim dintre toate unghiurile tuturor triunghiurilor construite, evitând astfel triunghiurile „subțiri”.
Triangulația Delaunay maximizează suma razelor cercurilor înscrise.
Triangulația Delaunay minimizează funcționalitatea Dirichlet discretă .
Triangulația Delaunay minimizează raza maximă a sferei de închidere minime.
Triangulația Delaunay pe plan are suma minimă a razelor cercurilor circumscrise triunghiurilor dintre toate triangulațiile posibile [1] .

Algoritmul Divide and Conquer

Acest algoritm se bazează pe metoda standard pentru mulți algoritmi de reducere a unei probleme complexe la altele mai simple, în care soluția este evidentă. Algoritmul în sine constă din 2 pași: $N>1$

Împărțirea setului original în seturi mai mici. Pentru a face acest lucru, desenăm linii verticale sau orizontale în mijlocul setului și deja în raport cu aceste linii împărțim punctele în două părți aproximativ de-a lungul . După aceea, pentru fiecare grup de puncte, începem recursiv procesul de împărțire. $N/2$
Unirea triangulațiilor optime. În primul rând, se găsesc două perechi de puncte, ale căror segmente, împreună cu triangulațiile construite, formează o figură convexă. Ele sunt conectate prin segmente, iar unul dintre segmentele obținute este ales ca început pentru bypass-ul ulterioar. Bypass-ul este următorul: pe acest segment, se pare că „umflam bula” spre interior până la primul punct la care ajunge cercul de umflare al „bulei”. Punctul găsit este legat de punctul segmentului care nu a fost conectat la acesta. Segmentul rezultat este verificat pentru intersecție cu segmente de triangulație deja existente, iar în cazul intersecției, acestea sunt îndepărtate din triangulație. După aceea, noul segment este luat drept început pentru o nouă „bulă”. Ciclul se repetă până când începutul coincide cu al doilea segment al carcasei convexe.

Complexitatea împărțirii mulțimii , îmbinării - pentru fiecare îmbinare, complexitatea finală a algoritmului - [2] . $O(\log N)$ $PE)$ $O(N\log N)$

Variații și generalizări

În spațiul tridimensional, o construcție similară este posibilă cu cercuri înlocuite cu sfere.
Generalizările sunt, de asemenea, folosite la introducerea altor metrici decât euclidiene .
Una dintre proprietățile triangulației Delaunay - suma minimă a razelor cercurilor circumscrise - poate fi aplicată așa-numitei triangulații Delaunay restrânse . Există n puncte, unele dintre muchiile de triangulație au fost deja desenate; trageți restul astfel încât suma razelor cercurilor circumscrise să fie cea mai mică.

Aplicație

Arborele de acoperire euclidian minim este garantat a fi pe o triangulație Delaunay, așa că unii algoritmi folosesc triangulația. De asemenea, prin triangulația Delaunay , problema vânzătorului ambulant euclidian este aproximativ rezolvată .

În interpolarea 2D , triangulația Delaunay împarte planul în cele mai groase triunghiuri posibile, evitând unghiurile prea ascuțite și prea obtuze. Din aceste triunghiuri se poate construi, de exemplu, interpolarea biliniară .

Metoda elementelor finite , o metodă pentru rezolvarea numerică a ecuațiilor diferențiale parțiale, este extrem de versatilă, iar odată cu creșterea puterii computerelor și dezvoltarea bibliotecilor standard, devine din ce în ce mai populară. Cu toate acestea, construcția unei rețele cu elemente finite a rămas până de curând lucru manual. În majoritatea variantelor metodei elementelor finite, eroarea este invers proporțională cu sinusul unghiului de plasă minim sau maxim, astfel încât mulți algoritmi de plasare automată folosesc triangulația Delaunay.

Vezi și

Cvasitriangulare

Note

↑ Skvortsov, 2002 , teorema 3, p. unsprezece.
↑ Skvortsov, 2002 , capitolul 3, algoritmul 3.1.

Literatură

Skvortsov A. V. Triangulația Delaunay și aplicarea acesteia . - Tomsk: Editura Universității din Tomsk, 2002. - 128 p. — ISBN 5-7511-1501-5 .
Skvortsov A. V., Mirza N. S. Algoritmi pentru construirea și analiza triangulației . - Tomsk: Editura Universității din Tomsk, 2006. - 168 p. — ISBN 5-7511-2028-0 .