Диаграмма Вороного

Utrujena cesta pod Rožnikom v Ljubljani

Kjer je konec asflata Jamnikarjeve ceste, gre pot naprej po makadamu, ki so mu nedavno zravnali velike luknje, na levo stojijo zapornice Biotehnične fakultete. Tam je površina ceste temeljito razpokana s pajčevinastimi vzorci, ki sem jih zbral v spodnjo mrežo podrobnih slik:

Zakaj je cesta tako razpokana? No, čas pozoba večino človekovih nevzdrževanih objektov, težnost, zaporedni cikli letnih časov ter zmrzovanja in taljenja vode uničijo cestišča in razjedo stavbe. Že, ampak zakaj prav takšne poškodbe? Tega ne vem dovolj dobro, me pa vzorci spomnijo na nekaj, čemur pravimo v matematiki Voronojevi diagrami:

Voronojevi diagrami: pri sto naključno posejanih točkah in pri ogliščih enakostraničnih trikotnikov, kjer nastane satovje; red semenskih točk botruje redu celic, to je logično

Diagrame se veliko uporablja, nikakor ne samo v teoretični matematiki. (Naslov zapisa v cirilici pomeni “figure Voronoja”, imenovane po ukrajinskem matematiku Georgiju Voronoju.) Imajo zanimivo zgodovino — zanimiv je primer zdravnika Johna Snowa, kako je določil pogubno vodno pumpo v času izbruha kolere v Londonu leta 1854 — diagrame se luštno ponazori z delitvijo zemlje.

Imejmo veliko zemljišče pravokotne oblike, ki ga moramo razdeliti med dva lastnika tako, da ni noben košček zemlje enega lastnika bližji hiši drugega (bele pike na sliki). Preprosto razpade zemljišče na dve posesti, ki pripadata posameznim hišam, in vsak košček zemlje je bližji svoji hiši kot pa drugi. Tega ni težko narisati, ker samo potegnemo pravokotnico na polovici zveznice hiš. In če so hiše tri? Potegnemo pravokotnice na tri zveznice, pravokotnice pa se sekajo v skupni točki, Voronojevi točki, ki je torej tu tromeja.

Razmejitve pri: treh, petih in 50-ih hišah

In če je točk, recimo tisoč? Bi potegnili več pravokotnice … No, delo raje prepustimo računalniku, ki je tu zelo uporaben. Posebej se izkaže pri ponavljanju. Recimo: da so vsi lastniki razen enega zadovoljni s krajem, kjer stoji njihova hiša, “nemirni” lastnik pa seli svojo po zemljišču. Spreminjajoča delitev zemlje je potem takšna:

Preseneti zdaj koga podatek, da se Voronojeve diagrame uporablja pri proučevanju ozemlja živali in pri postavljanju storitvenih podružnic, kot so McDonaldsi?

V splošnem pridejo v poštev, kjer iz množice točk-semen raste “nekaj” v vseh smereh pri enakih hitrostih; recimo kulturni vplivi v antropoloških študijah, ozemeljsko “tekmovanje” rastlinja v biologiji ali pa zlaganje satelitskih slik v en velik mozaik (Google Maps).