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

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

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

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

У најједноставнијем и најпознатијем случају (приказано на првој слици), имамо коначан скуп тачака {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^[3] "све локације у Воронојевом многоуглу су ближе генераторној тачки у том многоуглу него било којој другој генераторној тачки у Еуклидској равни".

Илустрација

Као једноставну илустрацију, размотримо групу продавница у неком граду. Претпоставимо да желимо да проценимо број купаца за дату продавницу. Ако је све остало исто (цена, производи, квалитет услуге, итд.), разумно је претпоставити да купци бирају своју продавницу на основу удаљености: отићи ће у продавницу која им је најближа. У овом случају Воронојева ћелија $\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 тачака у две различите метрике

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

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

Особине

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

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

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

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

Неформална употреба Воронојевих дијаграма се може срести још код Декарта 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.^[6]^[7]

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

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

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

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

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

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

Примене

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

Види још

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

Референце

^ Aurenhammer, Franz (1991). „Voronoi diagrams—a survey of a fundamental geometric data structure”. ACM Computing Surveys. 23 (3): 345—405. S2CID 4613674. doi:10.1145/116873.116880.
^ Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (1991). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2nd изд.). Wiley. ISBN 978-0-471-98635-5.
^ Q.T.Tran; D.Tainar; M.Safar (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. стр. 357. ISBN 978-3-642-03721-4.
^ Reem, Daniel (2009). „An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces”. 2009 Sixth International Symposium on Voronoi Diagrams. стр. 144—152. ISBN 978-1-4244-4769-5. S2CID 24930500. doi:10.1109/ISVD.2009.23.
^ Reem, Daniel (2011). „The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites”. Proceedings of the twenty-seventh annual symposium on Computational geometry. стр. 254—263. ISBN 9781450306829. S2CID 14639512. arXiv:1103.4125  . doi:10.1145/1998196.1998234.
^ Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third изд.). Springer-Verlag. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
^ Skyum, Sven (1991). „A simple algorithm for computing the smallest enclosing circle”. Information Processing Letters. 37 (3): 121—125. doi:10.1016/0020-0190(91)90030-L.
^ S. Arya, T. Malamatos, and D. M. Mount,Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002). pp. 721–730.
^ Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). „Uncertain Voronoi Diagram”. Information Processing Letters. Elsevier. 109 (13): 709—712. doi:10.1016/j.ipl.2009.03.007.
^ van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2011), Navigation Meshes for Realistic Multi-Layered Environments (PDF), International Conference on Intelligent Robots and Systems, IEEE/RSJ, стр. 3526—3532
^ Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third изд.). Springer-Verlag. ISBN 978-3-540-77974-2. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.

Литература

Q.T.Tran; D.Tainar; M.Safar (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. стр. 357. ISBN 978-3-642-03721-4.
Berg, Mark de; Kreveld, Marc van; 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. S2CID 116775758. 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 изд.). John Wiley. ISBN 978-0-471-98635-5.
Aurenhammer, Franz (септембар 1991). „Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure”. ACM Computing Surveys. 23 (3): 345—405. S2CID 4613674. doi:10.1145/116873.116880.
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. ISBN 978-1-4244-4769-5. 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: Reem, Daniel (2011). „The geometric stability of Voronoi diagrams with respect to small changes of the sites”. arXiv:1103.4125  . , Extended abstract: Reem, Daniel (2011). „The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites”. Proceedings of the twenty-seventh annual symposium on Computational geometry. стр. 254—263. ISBN 9781450306829. S2CID 14639512. arXiv:1103.4125  . doi:10.1145/1998196.1998234. .
Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, and Otfried (2000). Computational Geometry (2nd revised изд.). Springer-Verlag. ISBN 978-3-540-65620-3. Chapter 7: Voronoi Diagrams: pp. 147–163. Includes a description of Fortune's algorithm.
Klein, Rolf (1989). „Abstract voronoi diagrams and their applications”. Computational Geometry and its Applications. Lecture Notes in Computer Science. 333. Springer-Verlag. стр. 148—157. ISBN 978-3-540-52055-9. doi:10.1007/3-540-50335-8_31.

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

[1] Aurenhammer, Franz (1991). „Voronoi diagrams—a survey of a fundamental geometric data structure”. ACM Computing Surveys. 23 (3): 345—405. S2CID 4613674. doi:10.1145/116873.116880.

[2] Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (1991). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2nd изд.). Wiley. ISBN 978-0-471-98635-5.

[Tran09-3] Q.T.Tran; D.Tainar; M.Safar (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. стр. 357. ISBN 978-3-642-03721-4.

[Reem_alg-4] Reem, Daniel (2009). „An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces”. 2009 Sixth International Symposium on Voronoi Diagrams. стр. 144—152. ISBN 978-1-4244-4769-5. S2CID 24930500. doi:10.1109/ISVD.2009.23.

[Reem_geo_stable-5] Reem, Daniel (2011). „The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites”. Proceedings of the twenty-seventh annual symposium on Computational geometry. стр. 254—263. ISBN 9781450306829. S2CID 14639512. arXiv:1103.4125  . doi:10.1145/1998196.1998234.

[berg2008-6] Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third изд.). Springer-Verlag. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.

[7] Skyum, Sven (1991). „A simple algorithm for computing the smallest enclosing circle”. Information Processing Letters. 37 (3): 121—125. doi:10.1016/0020-0190(91)90030-L.

[8] S. Arya, T. Malamatos, and D. M. Mount,Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002). pp. 721–730.

[9] Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). „Uncertain Voronoi Diagram”. Information Processing Letters. Elsevier. 109 (13): 709—712. doi:10.1016/j.ipl.2009.03.007.

[10] van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2011), Navigation Meshes for Realistic Multi-Layered Environments (PDF), International Conference on Intelligent Robots and Systems, IEEE/RSJ, стр. 3526—3532

[automatski_generisano1-11] Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third изд.). Springer-Verlag. ISBN 978-3-540-77974-2. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]