Delaunay-triangulering

Delaunay- triangulering er en triangulering for et givet sæt af punkter S på en plan, hvor for enhver trekant alle punkter fra S , bortset fra de punkter, der er dens toppunkter, ligger uden for cirklen beskrevet omkring trekanten. Benævnt DT( S ) . Først beskrevet i 1934 af den sovjetiske matematiker Boris Delaunay .

Egenskaber

Delaunay-trianguleringen svarer en-til-en til Voronoi-diagrammet for det samme sæt punkter.
Som en konsekvens: Hvis der ikke er fire punkter på samme cirkel, er Delaunay-trianguleringen unik.
Delaunay-triangulering maksimerer minimumsvinklen blandt alle vinkler af alle konstruerede trekanter og undgår derved "tynde" trekanter.
Delaunay-triangulering maksimerer summen af radierne af de indskrevne cirkler.
Delaunay-trianguleringen minimerer den diskrete Dirichlet-funktion .
Delaunay-triangulering minimerer den maksimale radius af den mindste omsluttende kugle.
Delaunay-triangulering på planet har minimumsummen af radius af cirkler omskrevet om trekanter blandt alle mulige trianguleringer [1] .

Divide and Conquer-algoritme

Denne algoritme er baseret på standarden for mange algoritmer metode til at reducere et komplekst problem til simplere, hvor løsningen er indlysende. Selve algoritmen består af 2 trin: $N>1$

Opdeling af det originale sæt i mindre sæt. For at gøre dette tegner vi lodrette eller vandrette linjer i midten af sættet, og allerede med hensyn til disse linjer deler vi punkterne i to dele omtrent langs . Derefter starter vi rekursivt divisionsprocessen for hver gruppe af point. $N/2$
Forening af optimale trianguleringer. Først findes to par punkter, hvis segmenter sammen med de konstruerede triangulationer danner en konveks figur. De er forbundet med segmenter, og et af de opnåede segmenter er valgt som begyndelsen for den efterfølgende bypass. Bypasset er som følger: på dette segment ser det ud til, at vi "oppuster boblen" indad til det første punkt, som "boblens" oppustede cirkel når. Det fundne punkt er forbundet med det punkt på segmentet, der ikke var forbundet med det. Det resulterende segment kontrolleres for skæring med allerede eksisterende trianguleringssegmenter, og i tilfælde af kryds fjernes de fra trianguleringen. Derefter tages det nye segment som begyndelsen til en ny "boble". Cyklusen gentages, indtil begyndelsen falder sammen med det andet segment af det konvekse skrog.

Kompleksiteten ved at opdele sættet , sammenføjning - for hver sammenføjning, den endelige kompleksitet af algoritmen - [2] . $O(\log N)$ $PÅ)$ $O(N\log N)$

Variationer og generaliseringer

I tredimensionelt rum er en lignende konstruktion mulig med cirkler erstattet af kugler.
Generaliseringer bruges også, når der indføres andre metrikker end euklidiske .
En af egenskaberne ved Delaunay-triangulering - minimumsummen af radius af omskrevne cirkler - kan anvendes på den såkaldte begrænsede Delaunay-triangulering . Der er n punkter, nogle af trianguleringskanterne er allerede tegnet; tegn resten, så summen af radierne af de omskrevne cirkler er den mindste.

Ansøgning

Det mindste euklidiske spændingstræ er garanteret på en Delaunay-triangulering, så nogle algoritmer bruger triangulering. Også gennem Delaunay-trianguleringen er det euklidiske rejsende sælgerproblem tilnærmelsesvis løst .

I 2D - interpolation opdeler Delaunay-triangulering planet i de tykkeste trekanter som muligt og undgår for skarpe og for stumpe vinkler. Ud fra disse trekanter kan man bygge for eksempel bilineær interpolation .

Finite element -metoden, en metode til numerisk løsning af partielle differentialligninger, er ekstremt alsidig, og med væksten i computernes kraft og udviklingen af standardbiblioteker bliver den mere og mere populær. Konstruktionen af et finite element mesh forblev dog indtil for nylig manuelt arbejde. I de fleste varianter af finite element-metoden er fejlen omvendt proportional med sinusen af den minimale eller maksimale mesh-vinkel, så mange af de automatiske mesh-algoritmer bruger Delaunay-triangulering.

Se også

Kvasitriangulering

Noter

↑ Skvortsov, 2002 , sætning 3, s. elleve.
↑ Skvortsov, 2002 , kapitel 3, algoritme 3.1.

Litteratur

Skvortsov A. V. Delaunay-triangulering og dens anvendelse . - Tomsk: Publishing House of Tomsk University, 2002. - 128 s. — ISBN 5-7511-1501-5 .
Skvortsov A. V., Mirza N. S. Algoritmer til konstruktion og analyse af triangulering . - Tomsk: Publishing House of Tomsk University, 2006. - 168 s. — ISBN 5-7511-2028-0 .