11. julij, 2008 | Borut Levart

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

Matematična meditacija ob koncu Jamnikarjeve ceste.
  • DELICIOUS
  • Google
  • RSS

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).

 


  • DELICIOUS
  • Google
  • RSS
7 x komentirano
  • Igor Đukanović je rekel/-la:

    Presneti Voronoj. A ni mogel ostati doma v Ukrajini in pustiti naše ceste pri miru. Mi imamo že dovolj problemov s tujci. Zlasti z Blairom, ki se štuli v premierjeve govore. Sram ga bodi.

  • xrayspex je rekel/-la:

    za vzorec bi utegnila biti odgovorna ena od različic benardove nestabilnosti - podoben vzorec v slanih puščavskih jezerih nastane prek nje. gre za to, da se v tankih slojih z znatnim temperaturnim gradientom pojavijo konvekcijski tokovi, ki se oblikujejo v regularno mrežo konvektivnih celic. mreža v idealiziranem primeru izkazuje 6-števno simetrijo, podobno voronejevemu diagramu najbolj desno zgoraj. ni mi pa čisto jasno, ali je primerjava s fizikalne plati legitimna. z geometrijske je. toliko kot namig in ugibanje hkrati.

  • opleteni jež je rekel/-la:

    prispevek je prava osvežitev v poplavi političnih in zateženih (serija: inteligenco o…) objav.
    slikce so lepe grafike, paša za oči. razpokan asfalt je estetika, a ne za voznike.

  • Tomo je rekel/-la:

    čim več takih prispevkov. Da vidimo kako se manifestira teorija v praksi:)

  • 1tastar je rekel/-la:

    Takih diagramov je na naših cestah kar precej!

  • Nik je rekel/-la:

    En predlog za temo, ki bi mene, pa verjetno še koga, precej zanimala: tlakovanja površin, neperiodična tlakovanja (Penrose, Wang) in njihov pomen v matermatiki/računalništvu/umetni inteligenci (aksiomatski sistemi, Turingov stroj). Pa bolj preprosto, tako za laike…

  • h je rekel/-la:

    kul.