„Диаграмма Вороного” – ten dziwny, być może dla niektórych wyglądający na zaszyfrowany, tytuł, to zapisana cyrylicą nazwa pewnego ciekawego pojęcia matematycznego, które chciałbym przybliżyć w tym wpisie. Tym, którzy nie mieli szczęścia zapoznać się z alfabetem i językiem rosyjskim, wyjaśniam, że chodzi o diagram Woronoja – rzecz prosta, aczkolwiek nietrywialna. A że dodatkowo jest atrakcyjna graficznie i szczególnie wpisuje się w kontekst mapowy, warto by pojawiła się na ekskursja.pl.

Dlaczego zdecydowałem się zapisać tytuł wpisu cyrylicą? Po to by w ten sposób oddać hołd całej grupie matematyków rosyjskich. Każdy student politechniki będzie kojarzył (tzn. powinien kojarzyć jeśli chce skończyć studia) Markowa, Czebyszewa, Lapunowa i kilku innych. Być może właściwej byłoby mówić o grupie matematyków z obszaru Imperium Rosyjskiego, bo np. sam Georgij Woronow był Ukraińcem. Takie to były czasy i nie ma się czemu dziwić, że członkami (najczęściej korespondencyjnymi) Rosyjskiej Akadami Nauk w Petersburgu, byli tacy wybitni Polacy jak H. Sienkiewicz, Maria Skłodowska-Curie, Samuel B. Linde czy Jan Śniadecki.

Co do samego Woronoja to warto w tym miejscu nadmienić, że był on przez pewien czas profesorem Uniwersytetu Warszawskiego, a jego uczniem był m.in. Wacław Sierpiński.

Poznajemy diagramy Woronoja

Diagram Woronoja to, dla danego zbioru punktów, taki podział płaszczyzny, by dla każdego punktu z tego zbioru powstała „komórka” zawierająca wszystkie punkty, dla których jest to punkt najbliższy.

Taki podział dla losowego zbioru punktów wygląda następująco:

[do-svg style=”border: solid; border-color: white;” width=”630px” height=”420px” svg_path=”/wp-content/uploads/2016/04/woronoj.svg” alt_path=”/wp-content/uploads/2016/04/woronoj.png” alt=”Diagram Woronoja”]

Dla przestrzeni dwuwymiarowej i „standardowej” definicji odległości, komórki Woronoja są wielokątami wypukłymi. Nie ma w nim „dziur”, bo dla każdego punktu płaszczyzny istnieje w danym zbiorze punkt, który jest najbliższy (lub kilka w takiej samej odległości).

Diagram Woronoja na mapie

Zastanówmy się, jak wyglądałyby podział Polski na województwa, gdyby kryterium podziału była odległość do najbliższego miasta wojewódzkiego? Byłby to oczywiście diagram Woronoja, dla którego zadanymi punktami są miasta wojewódzkie. W przypadku województw: kujawsko-pomorskiego i lubuskiego przyjąłem, że punktem, od którego liczona jest odległość jest punkt pomiędzy miastem, które jest siedzibą wojewody i miastem, które jest siedzibą sejmiku.

Taki, bardziej „sprawiedliwy” podział wygląda następująco:

Jak widać nie jest on wcale bardzo odległy od obowiązującego podziału. Terytorialnie wydaje się, że mazowieckie trochę zakrzywia czasoprzestrzeń ściągając do siebie więcej powiatów niż wynikałoby to z ich odległości do stolicy.

Co dalej?

Tym krótkim wpisem nie wyczerpałem wszystkich ciekawostek związanych Woronojem i jego diagramami. Warto zobaczyć jak efektywnie konstruować takie diagramy (algorytm Fortuny) i poczytać (tutaj) o zastosowaniach m.in. jak ten koncept przydał się podczas analizy przyczyn rozprzestrzeniania się cholery w Londynie w 1854r.

Teoretycy mogą pozastanawiać się, jak wyglądają komórki Woronoja w trzech i więcej wymiarach, lub w przypadku gdy inaczej zdefiniujemy odległość.