Delaunay triangulering

Delaunay- triangulering är en triangulering för en given uppsättning punkter S på ett plan, där för varje triangel alla punkter från S , förutom de punkter som är dess hörn, ligger utanför cirkeln som beskrivs runt triangeln. Betecknas DT( S ) . Beskrevs första gången 1934 av den sovjetiske matematikern Boris Delaunay .

Egenskaper

Delaunay-trianguleringen motsvarar en-till-en- diagrammet Voronoi för samma uppsättning punkter.
Som en följd: om inga fyra punkter ligger på samma cirkel är Delaunay-trianguleringen unik.
Delaunay-triangulering maximerar minimivinkeln bland alla vinklar för alla konstruerade trianglar, och undviker därigenom "tunna" trianglar.
Delaunay-triangulering maximerar summan av radierna för de inskrivna cirklarna.
Delaunay-trianguleringen minimerar den diskreta Dirichlet-funktionen .
Delaunay-triangulering minimerar den maximala radien för den minsta omslutande sfären.
Delaunay-triangulering på planet har den minsta summan av radier av cirklar omskrivna kring trianglar bland alla möjliga trianguleringar [1] .

Dela och erövra algoritm

Denna algoritm är baserad på standardmetoden för många algoritmer för att reducera ett komplext problem till enklare, där lösningen är uppenbar. Algoritmen i sig består av 2 steg: $N>1$

Dela upp originaluppsättningen i mindre uppsättningar. För att göra detta ritar vi vertikala eller horisontella linjer i mitten av uppsättningen och redan med avseende på dessa linjer delar vi punkterna i två delar ungefär längs . Efter det, för varje grupp av poäng, startar vi rekursivt divisionsprocessen. $N/2$
Förening av optimala trianguleringar. Först hittas två par punkter, vars segment tillsammans med de konstruerade trianguleringarna bildar en konvex figur. De är förbundna med segment, och ett av de erhållna segmenten väljs som början för den efterföljande förbikopplingen. Förbikopplingen är som följer: på detta segment verkar vi "blåsa upp bubblan" inåt till den första punkten som "bubblans" uppblåsningscirkel når. Den hittade punkten är kopplad till punkten i segmentet som inte var kopplad till den. Det resulterande segmentet kontrolleras för korsning med redan existerande trianguleringssegment, och i händelse av korsning tas de bort från trianguleringen. Därefter tas det nya segmentet som början på en ny "bubbla". Cykeln upprepas tills början sammanfaller med det andra segmentet av det konvexa skrovet.

Komplexiteten i att dela upp uppsättningen , sammanfoga - för varje sammanfogning, den slutliga komplexiteten för algoritmen - [2] . $O(\log N)$ $PÅ)$ $O(N\log N)$

Variationer och generaliseringar

I det tredimensionella rummet är en liknande konstruktion möjlig med cirklar ersatta av sfärer.
Generaliseringar används också när man introducerar andra mått än euklidiska .
En av egenskaperna hos Delaunay-trianguleringen - minimisumman av radier av omskrivna cirklar - kan appliceras på den så kallade begränsade Delaunay-trianguleringen . Det finns n punkter, några av trianguleringskanterna har redan ritats; rita resten så att summan av radierna för de omskrivna cirklarna är som minst.

Applikation

Det minsta euklidiska spännträdet är garanterat på en Delaunay-triangulering, så vissa algoritmer använder triangulering. Dessutom, genom Delaunay-trianguleringen , är problemet med euklidiska resande försäljare ungefär löst .

I 2D -interpolation delar Delaunay-trianguleringen upp planet i de tjockaste trianglarna som möjligt, och undviker för skarpa och för trubbiga vinklar. Från dessa trianglar kan man bygga till exempel bilinjär interpolation .

Den finita elementmetoden , en metod för numerisk lösning av partiella differentialekvationer, är extremt mångsidig, och med tillväxten av datorernas kraft och utvecklingen av standardbibliotek blir den mer och mer populär. Tills nyligen förblev dock konstruktionen av ett ändligt elementnät manuellt arbete. I de flesta varianter av finita elementmetoden är felet omvänt proportionellt mot sinus för den minimala eller maximala maskvinkeln, så många av de automatiska mesh-algoritmerna använder Delaunay-triangulering.

Se även

Kvasitriangulering

Anteckningar

↑ Skvortsov, 2002 , sats 3, sid. elva.
↑ Skvortsov, 2002 , kapitel 3, algoritm 3.1.

Litteratur

Skvortsov A. V. Delaunay-triangulering och dess tillämpning . - Tomsk: Publishing House of Tomsk University, 2002. - 128 sid. — ISBN 5-7511-1501-5 .
Skvortsov A. V., Mirza N. S. Algoritmer för att konstruera och analysera triangulering . - Tomsk: Publishing House of Tomsk University, 2006. - 168 sid. — ISBN 5-7511-2028-0 .