Воронојев дијаграм

20 тачака и њихове Воронојеве ћелије (већа верзија испод).

У математици, Воронојев дијаграм је партиционисање равни у области засновано на удаљености од тачака из посебног подскупа равни. Тај скуп тачака (званих семена, положаји, или генератори) је одређен унапред, и за сваки генератор постоји одговарајућа област која се састоји од свих тачака које су ближе том генератору него било ком другом. Ове области се називају Воронојеве ћелије.

Назване су по Георгију Вороноју, и још се називају Воронојева теселација, Воронојева декомпозиција, Воронојево партиционисање, или Дирихлеова теселација (по Јохан Петер Густав Лежен Дирихле). Воронојеви дијаграми имају практичну и теоријску употребу у великом броју области, пре свега у науци и технологији, али и ликовној уметности.

Најједноставнији случај

У најједноставнијем и најпознатијем случају (приказано на првој слици), имамо коначан скуп тачака {p₁, …, p_n} у Еуклидској равни. У овом случају сваки генератор је једноставна тачка и њене одговарајуће Воронојеве ћелије (познате и као Воронојеве области или Дирихлеове ћелије) R_k се састоји од сваке тачке чија је удаљеност до p_k мања или једнака од удаљености до било ког другог генератора. Свака таква ћелија је добијена као пресек полупростора, па је стога конвексан многоугао. Сегменти Воронојевог дијаграма су све тачке у равни које су подједнако удаљене од два најближа генератора. Воронојева темена су тачке подједнако удаљене од три (или више) генератора.

Формална дефиниција

Нека је $\scriptstyle X$ простор (непразан скуп) са метриком $\scriptstyle d$. Нека је $\scriptstyle K$ скуп индекса и нека је $\scriptstyle (P_{k})_{k\in K}$ n-торка (уређена колекција) непразних подскупова (генератора) у простору $\scriptstyle X$. Воронојева ћелија, или Воронојева област, $\scriptstyle R_{k}$, која одговара генератору $\scriptstyle P_{k}$ је скуп свих тачака у $\scriptstyle X$ чија удаљеност до $\scriptstyle P_{k}$ није већа од удаљености до других генератора $\scriptstyle P_{j}$, где је $\scriptstyle j$ било који индекс различит од $\scriptstyle k$. Другим речима, ако $\scriptstyle d(x,\,A)\;=\;\inf\{d(x,\,a)\mid a\,\in \,A\}$ означава растојање између тачке $\scriptstyle x$ и подскупа $\scriptstyle A$, онда

$R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}$

Воронојев дијаграм је једноставно n-торка ћелија $\scriptstyle (R_{k})_{k\in K}$. У принципу неки од генератора се могу пресецати и чак поклапати (пример је описан испод за генераторе који представљају продавнице), али обично се претпоставља да су раздвојени. Такође, бесконачно много генератора је дозвољено у дефиницији (има примену у геометрији бројева и кристалографији), али опет у многим случајевима се разматра само коначан број генератора.

У посебном случају када је простор коначно-димензиони Еуклидски простор, сваки генератор је тачка, има коначно много тачака и све су различите, онда су Воронојеве ћелије ковексни политопи и могу бити представљене помоћу темена, ивица, 2-димензионих страна, итд. Некада је тако индукована структура Воронојев дијаграм, међутим, генерално Воронојеве ћелије не морају бити ни конвексне ни повезане.

У уобичајеном Еуклиском простору, можемо поново написати формалну дефиницију. Сваком Воронојевом многоуглу $\scriptstyle R_{k}$ одговара генераторна тачка $\scriptstyle P_{k}$. Нека је $\scriptstyle X$ скуп свих тачака у еуклидском простору. Нека је $\scriptstyle P_{1}$ тачка која генерише Воронојеву област $\scriptstyle R_{1}$, $\scriptstyle P_{2}$ генерише $\scriptstyle R_{2}$, $\scriptstyle P_{3}$ генерише $\scriptstyle R_{3}$, и тако даље. Тада по Tran et al "све локације у Воронојевом многоуглу су ближе генераторној тачки у том многоуглу него било којој другој генераторној тачки у Еуклидској равни".

Илустрација

Као једноставну илустрацију, размотримо групу продавница у неком граду. Претпоставимо да желимо да проценимо број купаца за дату продавницу. Ако је све остало исто (цена, производи, квалитет услуге, итд.), разумно је претпоставити да купци бирају своју продавницу на основу удаљености: отићи ће у продавницу која им је најближа. У овом случају Воронојева ћелија $\scriptstyle R_{k}$ за дату продавницу $\scriptstyle P_{k}$ може бити искоришћена за грубу процену броја потенцијалних купаца који долазе у ту продавницу.

До сада смо претпостављали да је растојање између тачака мерено Еуклидским растојањем:

$\ell _{2}=d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}$

Међутим, ако размотримо случај када купци одлазе у продавнице возилом и саобраћајне траке су паралелне $x$ и $y$ осама, као на Менхетну, тада је реалистичнија метрика $\ell _{1}$, дата са $d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|$.

Воронојев дијаграм са 20 тачака у две различите метрике

Еуклидско растојање

Менхетн растојање

Особине

• Дуални граф за Воронојев дијаграм (у случају Еуклидског простора са тачкама генераторима) одговара Делонијевој триангулацији за исти скуп тачака.
• Најближи пар тачака одговара двема суседним ћелијама у Воронојевом дијаграму
• Ако је дата група различитих тачака у равни, тада су две тачке суседне у конвексном омотачу ако и само ако њихове Воронојеве ћелије деле бесконачно дугу страницу.
• Ако је простор нормиран и удаљеност до сваког генератора је достижна (нпр. када је генератор компактан скуп или затворена кугла), онда се свака Воронојева ћелија може представити као унија сегмената линија које потичу из генератора.

Ово својство не мора нужно да важи уколико удаљеност није достижна.

• У релативно општим условима (ако је простор бесконачно димензиони равномерно конвексни простор, може бити бесконачно много генератора, итд) Воронојеве ћелије показују одређено својство стабилности: мале промене у облику генератора (нпр. промене изазване транслацијом или дисторзијом) производе мале промене облика Воронојевих ћелија. Ово је геометријска стабилност Воронојевих дијаграма. Ово својство не мора да важи у општем случају, чак иако је простор дводимензиони (али не равномерно конвексан, и посебно нееуклидски) и генератори су тачке.

Историја и истраживања

Неформална употреба Воронојевих дијаграма се може срести још код Декарта 1644. Дирихле је користио 2-димензионе и 3-димензионе Воронојеве дијаграме у својој студији о квадратним формама 1850. Британски физичар Џон Сноу је користио Воронојеве дијаграме 1854 да илуструје како је већина људи која је умрла у епидемији колере у Сохоу 1854 живела ближе воденој пумпи у Броад улици него било којој другој пумпи. Воронојеви дијаграми су названи по Украјинском математичару Георгију Федосијевичу Вороноју који је проучавао и дефинисао n-димензиони случај 1908. Воронојеви дијаграми који се користе у геофизици и метеорологији за анализу просторно дистрибуираних података (као што је мерење падавина) се називају Тиесенови полигони по Америчком метереологу Алфреду Х. Тиесену. У физици кондензоване материје такве теселације су познате и као Wigner–Seitz ћелије. Друга еквивалентна имена за овај концепт (или његов посебан случај) : Воронојеви полиедри, Воронојеви полигони, домени утицаја, Воронојева декомпозиција, Дирихлеова теселација.

Воронојеви дијаграми вишег реда

Иако је нормална Воронојева ћелија дефинисана као скуп тачака најближих једној одређеној тачки у S, Воронојева ћелија n-ог реда је дефинисана као скуп тачака које имају одређен скуп од n тачака у S као својих n најближих комшија. Воронојеви дијаграми вишег реда такође даље деле простор.

Воронојеви дијаграми вишег реда могу бити дефинисани рекурзивно. За генерисање Воронојевог дијаграма n-ог реда из скупа  S, почиње се са дијаграмом(n − 1)-ог реда и замењује свака ћелија генерисана са X = {x₁, x₂, ..., x_n−1} са Воронојевим дијаграмом генерисаним скупом  S − X.

Воронојев дијаграм најудаљеније тачке

За скуп од n тачака Воронојев дијаграм (n − 1)-ог реда се зове Воронојев дијаграм најудаљеније тачке.

За дати скуп тачака П = {p₁, p₂, ..., p_n} Воронојев дијаграм најудаљеније тачке дели раван на ћелије у којима је иста тачка из P најудаљенија. Приметимо да тачка из P има ћелију у Воронојевом дијаграму најудаљеније тачке ако и само ако је теме конвексног омотача од P. Према томе нека је H = {h₁, h₂, ..., h_k} конвексни омотач од P дефинишемо Воронојев дијаграм најудаљеније тачке као поделу равни на k ћелија, једну за сваку ћелију у H, са особином да тачка q лежи у ћелији која одговара генератору h_i ако и само ако dist(q, h_i) > dist(q, p_j) за свако p_j ∈ S и h_i ≠ p_j. где је dist(p, q) Еуклидско растојање између две тачке p and q.

Генерализација и варијације

Као што је речено у дефиницији, Воронојеве ћелије могу бити дефинисане и за друге метрике осим Еуклидске. Међутим може се десити да границе Воронојевих ћелија могу бити компликованије него у Еуклидском случају, јер се може десити да еквидистантно место за две тачке не буде потпростор димензије 1, чак ни у 2-димензионом случају.

приближни Воронојев дијаграм скупа тачака. Приметите измешане боје на границама Воронојевих ћелија.

Тежински Воронојев дијаграм је онај у ком функција пара тачака која дефинише Воронојеву ћелију је функција удаљености модификована за тежину додељену генераторним тачкама. За разлику од случаја када је Воронојева ћелија дефинисана користећи метрику, у овом случају неке од Воронојевих ћелија могу бити празне.

Воронојев дијагррам са n тачака у d-димензионом простору захтева $\scriptstyle O\left(n^{\left\lceil {\frac {1}{2}}d\right\rceil }\right)$ простора за складиштење. Зато, Воронојеви дијаграми често нису остварљиви за d > 2. Алтернатива је да се користе приближни Воронојеви дијаграми, где Воронојеве ћелије имају нејасне границе, које могу бити апроксимиране. Друга алтернатива је када су сви генератори нејасни кругови као резултат и ћелије постају нејасне.

Воронојеви дијаграми су такође повезани и са другим геометријским структурама које имају широку примену у компјутерским апликацијама. Поред тачака, неки дијаграми користе и линије и полигоне као генераторе. Тај принцип користе нпр. навигационе мреже које служе за проналажење путева у великим просторима. Навигациона мрежа може бити и генерализована да подржи 3Д окружења као што су аеродроми или зграде са више спратова.

Примене

• У геометрији, Воронојеви дијаграми се могу користити за проналажење највећег празног круга усред скупа тачака и у околном полигону; нпр. изградња новог супермаркета што даље од постојећих, али у истом граду.
• У епидемиологији, Воронојеви дијаграми могу бити коришћени да прикажу корелацију извора инфекција у епидемијама. Једна од раних примена Воронојевих дијаграма је била имплементирана од стране Џона Сноа за проучавање епидемије колере 1854 у Сохоу у Енглеској. Он је приказао однос између области на мапи Лондона користећи одређену пумпу за воду, и области са највише смрти за време епидемије.
• Структура података за локацију тачке може бити формирана на основу Воронојевог дијаграма ради одговора на упите за претраживање најближег суседа где се тражи објекат који је најближи датој тачки. Претраживање најближег суседа има бројне примене. На пример, уколико нам је потребно да пронађемо најближу болницу, или најсличнији објекат у бази података.
• Воронојеви дијаграми заједно са Воронојевим дијаграмима најудаљеније тачке се користе као ефикасни алгоритми за израчунавање округлости скупа тачака.
• У хидрологији, Воронојеви дијаграми се користе за израчунавање количине падавина на одређеном подручју, базирано на серији мерења у одређеним тачкама. Када се користе на овај начин, обично се називају Тиесенови полигони.
• У екологији, Воронојеви дијаграми се користе за проучавање трендова раста шума и могу бити такође коришћени у развоју модела за предвиђање шумских пожара.
• У рударству, Воронојеви дијаграми се користе за процену резерви вредних материјала, минерала или других ресурса. Истраживачке бушотине се користе као скуп тачака у Воронојевим дијаграмима.
• У проучавању навигације робота, Воронојеви дијаграми се користе за проналажење чисте путање. Ако су тачке препреке, онда су ивице дијаграма путање најудаљеније од препрека.

Види још

Алгоритми

• Фортунов алгоритам, O(n log(n)) алгоритам за генерисање Воронојевог дијаграма из скупа тачака у равни

Литература

• Mark de Berg; Marc van Kreveld; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third изд.). Springer-Verlag. 
• G. Lejeune Dirichlet (1850). „Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen”. Journal für die Reine und Angewandte Mathematik. 40: 209—227. 
• Voronoi, Georgy (1908). „Nouvelles applications des paramètres continus à la théorie des formes quadratiques”. Journal für die Reine und Angewandte Mathematik. 133 (133): 97—178. doi:10.1515/crll.1908.133.97. 
• Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, 671 pages. ISBN 0-471-98635-6.
• Aurenhammer, Franz (септембар 1991). „Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure”. ACM Computing Surveys. 23 (3): 345—405. doi:10.1145/116873.116880. CS1 одржавање: Формат датума (веза)
• Reem, Daniel (2009). „An algorithm for computing Voronoi diagrams of general generators in general normed spaces”. Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009). стр. 144—152. doi:10.1109/ISVD.2009.23. 
• Daniel Reem (2011). The geometric stability of Voronoi diagrams with respect to small changes of the sites. Full version: arXiv 1103.4125 (2011), Extended abstract: in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ‏2011). стр. 254–263.
• Mark de Berg; Marc van Kreveld; Overmars, Mark; and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised изд.). Springer-Verlag. ISBN 3-540-65620-0.  Chapter 7: Voronoi Diagrams: ppp. 147–163. Includes a description of Fortune's algorithm.
• Klein, Rolf (1989). Abstract voronoi diagrams and their applications. Lecture Notes in Computer Science. 333. Springer-Verlag. стр. 148—157. doi:10.1007/3-540-50335-8_31. ISBN 3-540-52055-4. 

Спољашње везе

• Real time interactive Voronoi / Delaunay diagrams with draggable points, Java 1.0.2, 1996–1997
• Real time interactive Voronoi and Delaunay diagrams with source code
• Interactive Voronoi diagrams with Natural Neighbor Interpolation visualization (in WebGL)
• Demo for various metrics
• Mathworld on Voronoi diagrams
• Qhull for computing the Voronoi diagram in 2-d, 3-d, etc.
• Voronoi Diagrams: Applications from Archaeology to Zoology
• Voronoi Diagrams in CGAL, the Computational Geometry Algorithms Library
• Voronoi Web Site : using Voronoi diagrams for spatial analysis
• More discussions and picture gallery on centroidal Voronoi tessellations
• Voronoi Diagrams by Ed Pegg, Jr., Jeff Bryant, and Theodore Gray, Wolfram Demonstrations Project.
• Nice explanation of voronoi diagram and visual implementation of fortune's algorithm
• A Voronoi diagram on a sphere
• Plot a Voronoi diagram with Mathematica
• Voronoi software for shattering 3D geometry
• Hand-drawing Voronoi diagrams
• Overlaid Voronoi diagram of the United States based on state capitals
• Overlaid Voronoi diagram of the world based on national capitals