Voronoi diagram

Voronoi-diagrammet för en ändlig uppsättning punkter S på ett plan representerar en sådan uppdelning av planet, där varje område av denna partition bildar en uppsättning punkter som är närmare ett av elementen i uppsättningen S än någon annat element i uppsättningen [1] .

Uppkallad efter Georgy Feodosevich Voronoi , som studerade det allmänna n - dimensionella fallet 1908 [2] . Även känd som: Voronoi plattsättning, Voronoi plattsättning, Dirichlet plattsättning .

Historik

För första gången tillskrivs användningen av sådana strukturer till Descartes 1644. Dirichlet använde tvådimensionella och tredimensionella Voronoi-diagram i sitt arbete med kvadratiska former 1850.

Egenskaper

Den har en nära koppling och en-till-en-korrespondens med Delaunay-trianguleringen . Nämligen, om vi förbinder punkter med kanter vars Voronoi-regioner gränsar till varandra, kommer den resulterande grafen att vara en Delaunay-triangulering.

Konstruktionsalgoritmer

En enkel algoritm

Betrakta den vinkelräta bisektrisen av ett segment som förbinder ett par punkter och . $sid$ $q$

Denna vinkelrät delar upp planet i två halvplan och , och Voronoi-området för punkten p är helt inneslutet i en av dem, och området för punkten finns i den andra. Området för Voronoi - punkten sammanfaller med skärningspunkten mellan alla sådana halvplan : $H_{{pq}}$ $H_{{qp}}$ $q$ $V_{p}$ $sid$ $H_{{pq}}$

$V_{p}=\bigcap \limits _{q\in S/\{p\}}H_{pq}$ .

Således reduceras lösningen av problemet till beräkningen av en sådan skärningspunkt för varje punkt . Algoritmen kan implementeras med beräkningskomplexitet [3] . $sid$ $O(n^{4})$

Fortunes algoritm

Algoritmen är baserad på användningen av en svepande linje. Den svepande linjen är ett hjälpobjekt som representerar en vertikal rak linje. Vid varje steg i algoritmen konstrueras ett Voronoi-diagram för en uppsättning som består av en svepande linje och pekar till vänster. I detta fall består gränsen mellan Voronoi-området, linjen och punktområdena av segment av paraboler (eftersom platsen för punkter på samma avstånd från en given punkt och linjen är en parabel ). Den raka linjen rör sig från vänster till höger. Varje gång den passerar genom en annan punkt läggs denna punkt till den redan konstruerade delen av diagrammet. Att lägga till en punkt till ett diagram med hjälp av ett binärt sökträd har en komplexitet på , totala poäng och sortering av punkter efter koordinat kan göras i , så beräkningskomplexiteten för Fortunes algoritm är . $O(\log n)$ $n$ $x$ $O(n\log n)$ $O(n\log n)$

Rekursiv algoritm

Huvudidén med den rekursiva algoritmen är att använda den dynamiska programmeringsmetoden . Den initiala uppsättningen av punkter är uppdelad i två delmängder och , ett Voronoi-diagram konstrueras för var och en av dem, och sedan kombineras de resulterande diagrammen till ett. Uppdelningen av uppsättningen utförs med hjälp av en rät linje som delar planet i två halvplan, så att båda halvplanen innehåller ungefär samma antal punkter. Unionen av Voronoi diagram av uppsättningar och kan utföras i tid , så beräkningskomplexiteten av algoritmen är . $S$ $S_{1}$ $S_{2}$ $S$ $S_{1}$ $S_{2}$ $På)$ $O(n\log n)$

Generaliseringar

Ett Voronoi-diagram kan definieras på ett uppenbart sätt för en uppsättning punkter i ett godtyckligt euklidiskt utrymme , inte nödvändigtvis tvådimensionellt. Följande påstående gäller: i det dimensionella rymden kan antalet förenklingar av dimensionell Delaunay-triangulering av en uppsättning punkter nå . Därför är minneskostnaderna som krävs för att lagra det dubbla Voronoi-diagrammet av samma storleksordning. $k$ $k$ $n$ $O(n^{{\lceil {\frac k2}\rceil }})$

Ett Voronoi-diagram kan definieras för ett utrymme med en icke-euklidisk metrik . I det här fallet kanske gränserna mellan angränsande Voronoi-regioner inte är första ordningens grenrör (till exempel när man använder Manhattan-avståndet ).

Mängden S kan bestå inte bara av punkter utan också av alla objekt för vilka avståndet till en godtycklig punkt i planet bestäms. I det här fallet kallas elementen i mängden S platser. Ett exempel är Voronois polygondiagram , där platser är hörn och kanter på polygonen. Sådana diagram används för att konstruera medianaxlar och används ofta i bildanalysproblem. Gränsen för regionerna i Voronoi-polygondiagrammet är föreningen av linjesegment och paraboler.

Applikation

Voronoi-partitionen används i beräkningsmaterialvetenskap för att skapa syntetiska polykristallina aggregat. Används även i datorgrafik för att slumpmässigt dela in ytor.

Golds metod (eller "area stealing method") är en metod för att interpolera en funktion i 2D, som används till exempel inom geodesi. Ett Voronoi-diagram av alla punkter konstrueras, varefter den önskade punkten läggs till den. Den nya cellen "väljer" området från de befintliga; ju mer area lånat från ( x i , y i , z i ), desto större koefficient vid den punkten.

Voronoi-partitionen används också för att hitta den övre uppskattningen av det kromatiska talet för det euklidiska rummet ( Nelson-Erdős-Hadwiger-problemet ) av dimension 2 eller 3. Här är uppdelningen av planet i Voronoi-polygoner för ett givet gitter anses vara. Den bästa uppskattningen hittades för både 2-dimensionella och 3-dimensionella utrymmen när man övervägde en symmetrisk partition. Till exempel lägga ett plan med hexagoner (i det här fallet är en hexagon en Voronoi-polygon).

Se även

Länkar

Fortune's Algorithm Arkiverad 13 juni 2008 på Wayback Machine
Fortune Algorithm Visualizer

Källor

↑ F. Preparata, M. Sheimos. Computational Geometry: An Introduction. Arkivexemplar daterad 23 april 2011 på Wayback Machine - M .: Mir, 1989. S. 295
↑ G. F. Voronoi. Nouvelles applications des paramètres fortsätter à la théorie de formesatiques (franska) // Journal für die reine und angewandte Mathematik. - 1908. - Vol. 134 . - S. 198-287 .
↑ Voronoi diagram . MAXimal (26 januari 2009). Hämtad 8 juni 2021. Arkiverad från originalet 8 juni 2021. (ryska)