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

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

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

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

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

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

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

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

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

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

У уобичајеном Еуклиском простору, можемо поново написати формалну дефиницију. Сваком Воронојевом многоуглу одговара генераторна тачка . Нека је скуп свих тачака у еуклидском простору. Нека је тачка која генерише Воронојеву област , генерише , генерише , и тако даље. Тада по Tran et al[3] "све локације у Воронојевом многоуглу су ближе генераторној тачки у том многоуглу него било којој другој генераторној тачки у Еуклидској равни".

Илустрација[уреди]

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

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


Међутим, ако размотримо случај када купци одлазе у продавнице возилом и саобраћајне траке су паралелне и осама, као на Менхетну, тада је реалистичнија метрика , дата са .


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

Особине[уреди]

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

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

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

Историја и истраживања[уреди]

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

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

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

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

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

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

За дати скуп тачака П = {p1p2, ..., pn} Воронојев дијаграм најудаљеније тачке дели раван на ћелије у којима је иста тачка из P најудаљенија. Приметимо да тачка из P има ћелију у Воронојевом дијаграму најудаљеније тачке ако и само ако је теме конвексног омотача од P. Према томе нека је H = {h1h2, ..., hk} конвексни омотач од P дефинишемо Воронојев дијаграм најудаљеније тачке као поделу равни на k ћелија, једну за сваку ћелију у H, са особином да тачка q лежи у ћелији која одговара генератору hi ако и само ако dist(q, hi) > dist(q, pj) за свако pj ∈ S и hipj. где је dist(p, q) Еуклидско растојање између две тачке p and q.[6][7]

Генерализација и варијације[уреди]

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

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

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

Воронојев дијагррам са n тачака у d-димензионом простору захтева простора за складиштење. Зато, Воронојеви дијаграми често нису остварљиви за d > 2. Алтернатива је да се користе приближни Воронојеви дијаграми, где Воронојеве ћелије имају нејасне границе, које могу бити апроксимиране.[8] Друга алтернатива је када су сви генератори нејасни кругови као резултат и ћелије постају нејасне.[9]

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

Примене[уреди]

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

Види још[уреди]

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

Референце[уреди]

  1. Franz Aurenhammer . Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345–405, 1991
  2. 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. 1991. ISBN 978-0-471-98635-5.
  3. Q.T.Tran, D.Tainar and M.Safar. "Transactions on Large-Scale Data- and Knowledge-Centered Systems". 2009. ISBN 978-3-642-03721-4. стр. 357.
  4. Daniel Reem, An algorithm for computing Voronoi diagrams of general generators in general normed spaces, In Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009), (2009). стр. 144–152
  5. Daniel Reem, 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
  6. Mark de Berg; Marc van Kreveld; 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. , contains a simple algorithm to compute the farthest-point Voronoi diagram.
  8. S. Arya, T. Malamatos, and D. M. Mount,Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002). стр. 721-730.
  9. Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). „Uncertain Voronoi Diagram” (PDF). 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 
  11. Mark de Berg; Marc van Kreveld; 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.

Литература[уреди]

Спољашње везе[уреди]