Voronoi diagrams – inventor, method, applications

• Autorzy: Pokojski W. , Pokojska P.

Identyfikatory

DOI

10.2478/pcr-2018-0009

• Języki publikacji: EN

Abstrakty

EN

The article presents the person and works of Georgy Voronoi (1868–1908), the inventor of an original method of diagrams, a student of the famous mathematician Andrey Markov. Georgy Voronoi graduated from the Department of Physics and Mathematics at the University of St. Petersburg, and subsequently worked as a professor of mathematics at the Imperial University of Warsaw. One of his students was the future outstanding Polish mathematician Wacław Sierpiński. In his brief lifetime G. Voronoi published several important scientific articles on number theory. In an almost 100 page paper in French published in 1908 he described a method of diagrams, or polygons, which became known as the method of Voronoi diagrams. In the digital age this method and its modifications found new applications. The entry “Voronoi” is getting more popular on the Internet, and the method of Voronoi diagrams and its modifications are widely described in handbooks and scientific articles. The article presents application of the method in the most popular computer programs from the Geographic Information System (GIS) group and presents examples of its usage in research on geographic space in various scientific disciplines.

Słowa kluczowe

EN

Voronoi diagram; Voronoi Georgij; GIS; University of Warsaw

• Wydawca: Polskie Towarzystwo Geograficzne. Oddział Kartograficzny
• Czasopismo: Polish Cartographical Review
• Rocznik: 2018
• Tom: Vol. 50, No. 3
• Strony: 141--150
• Opis fizyczny: Bibliogr. 48 poz., rys., tab., zdj.

Twórcy

autor

Pokojski W.

• University of Warsaw, Faculty of Geography and Regional Studies Chair of Geomatics and Information Systems, Warsaw, Poland

autor

Pokojska P.

• University of Warsaw, Faculty of Geography and Regional Studies, Warsaw, Poland

Bibliografia

• Anton F., Gold C.M., Mioc D., 1998, Local coordinates and interpolation in a Voronoi diagram for a set of points and line segments. In: The Voronoi Conference on Analytic Number Theory and Space Tillings, pp. 9–12.
• Aurenhammer F., Edelsbrunner H., 1984, An optimal algorithm for constructing the weighted Voronoi diagram in the plane. “Pattern Recognition” Vol. 17 no. 2, pp. 251–257. https://doi.org/10.1016/0031-3203(84)90064-5
• Aurenhammer F., Klein R., Lee D.-T., 2013, Voronoi diagrams and Delaunay triangulations. Singapore: World Scientific Publishing.
• Awramiuk-Godun A., 2013, Rozmieszczenie obiektów sakralnych jako kryterium wyznaczania zasięgu krajobrazu pogranicza kulturowego. „Prace Komisji Krajobrazu Kulturowego” Nr 19, pp. 62–72.
• Bae W., Chwa K.Y., 2005, Shortest paths and Voronoi diagrams with transportation networks under general distances. Berlin, Heidelberg: Springer Verlag.
• Biografia Markow. (http://wazniak.mimuw.edu.pl/index.php?title=Biografia_Markow%2C_Andriej
• Bochenek A., Jasiński T., 2015, Zastosowanie algorytmu Woronoja do określenia dostępności terenów zieleni w wybranych, dużych miastach Europy. „Współczesne problemy i kierunki badawcze w geografii” T. 3, Instytut Geografii i Gospodarki Przestrzennej UJ, pp. 17–27.
• Candeloro M., Lekkas A.M., Sorensen A.J., 2017, A Voronoi-diagram-based dynamic path-planning system for underactuated marine vessels. “Control Eng. Pract.” Vol. 61, pp. 41–54. DOI: 10.1016/j. conengprac.2017.01.007
• Cosquer G., Hangouët J.F., 2003, Delimitation of land and sea boundaries: Geodetic and geometric bases. FIG Working Week 2003, Paris, France, April 13–17. https://www.fig.net/resources/proceedings/fig_proceedings/fig_2003/TS_20/PP20_1_Cosquer_Hangouet.pdf
• Dakowicz M., Gold C., 2002, Extracting meaningful slopes from terrain contours. In: Computational Science – ICCS 2002. Eds. S.P.M.A. Sloot, A.G. Hoekstra, C.J.K. Tan, J.J. Dongarra, “Lecture Notes in Computer Science” Vol. 2331. Berlin, Heidelberg: Springer.
• Descartes R., 1644, Le monde de M. Descartes ou le Traité de la Lumière. Paris.
• Dirichlet G.L., 1850, Über die Reduction der positieven quadratischen Formen mit drei unbestimmten ganzen Zahlen. „Journal für die Reine und Angewandte Mathematik” Vol. 40, pp. 209–227.
• Dong P., 2008, Generating and updating multiplicatively weighted Voronoi diagrams for point, line and polygon features in GIS. “Computers & Geosciences” Vol. 34, no. 4, pp. 411–421.
• Duda R., 2016, Matematyka. Nauki ścisłe i przyrodnicze na Uniwersytecie Warszawskimm. In: Dzieje Uniwersytetu Warszawskiego 1816-1915. Ed. T. Kizwalter, „Monumenta Universitatis Varsoviensis 1816–2016”, Warszawa: Wydawnictwa Uniwersytetu Warszawskiego.
• Gavrilova M., Ed. 2008, A Geometry-based approach to computational intelligence. “Studies in Computational Intelligence” 158. Springer.
• Gaździcki J., 1990, Systemy informacji przestrzennej. Warszawa: Państwowe Przedsiębiorstwo Wydawnictw Kartograficznych.
• Georgij Woronoj. https://ru.wikipedia.org/wiki
• Hurwic J., 2016, Wacław Sierpinski 1882–1969. In: Dzieje Uniwersytetu Warszawskiego 1816-1915. Ed. T. Kizwalter, „Monumenta Universitatis Varsoviensis 1816–2016”, Warszawa: Wydawnictwa Uniwersytetu Warszawskiego, p. 231.
• Karimi F., Delavar M.R., Mostafavi M.A., 2009, Space allocation of educational centers using multiplicatively weighted Voronoi diagram. ISPRS COST Workshop on Quality Scale and Analysis Aspects of City Models, Lund.
• Kisiała W., Rudkiewicz M., 2017, Zastosowanie diagramu Woronoja w badaniu przestrzennych wzorców rozmieszczenia i dostępności sklepów dyskontowych. „Przegląd Geograficzny” T. 89, nr 2, pp. 187–212.
• Kratko M.I., 2011, Heorhij Woronyj – matematyk ukraiński i polski. http://voronuy.at.ua/publ/heorhij_woronyj_matematyk_ukrainski_i_polski/1-1-0-48
• Ledoux H., 2007, Computing the 3D Voronoi diagram robustly: An easy explanation Voronoi diagrams in science and engineering. 2007. ISVD ’07. 4th International Symposium, pp. 117–129.
• Longley P.A., Goodchild M., Maguire D.J., Rhind D.W., 2005, Geographic Information Systems and Science. Chichester – New York: John Wiley & Sons, 342 pp.
• Lovacka S., 2008, The use of the Voronoi tessellation for purposes of service distribution districts delimitation (The example of the Prešov nodal region). „Folia Geographica” Vol. 12, pp. 163–171.
• MacTutor History of Mathematics. http://www-groups. dcs.st-and.ac.uk/~history/Biographies/Voronoy.html
• Magnuszewski A., 1999, GIS w geografii fizycznej. Warszawa: Wydawnictwo Naukowe PWN.
• Mathworks Documentation. Woronoi diagrams. https:// www.mathworks.com/help/matlab/math/voronoi-diagrams.html
• Miąso J., 1989, Trudne narodziny Politechniki Warszawskiej: (przyczynek do dziejów polityki naukowej w Królestwie Polskim). „Kwartalnik Historii Nauki i Techniki” T. 34, nr 4, pp. 777–818.
• Okabe A., Boots B., Sugihara K., Chiu S.N., 2009, Spatial tessellations: Concepts and applications of Voronoi diagrams. Chichester – New York: John Wiley & Sons.
• Rezende, F., Almeida R., and Nobre, F., 2000, Diagramas de Voronoi para a definicao de areas de abrangencia de hospitais publicos no Municıpio do Rio de Janeiro. „Cadernos de Saude Publica” T. 16, no. 2, pp. 467–475.
• Schiller J. 2005, Uniwersytet Warszawski. Czy Uniwersytet i czy w Warszawie? „Kwartalnik Historii Nauki i Techniki” T. 50, nr 2–4, pp. 25–58.
• Schiller-Walicka J., 2016, Cesarski Uniwersytet Warszawski: między edukacją a polityką 1869–1917. In: Dzieje Uniwersytetu Warszawskiego 1816-1915. Ed. T. Kizwalter, „Monumenta Universitatis Varsoviensis”, Warszawa: Wydawnictwa Uniwersytetu Warszawskiego, pp. 557–703.
• Schinzel A., 2016, Georgij Woronoj – Mistrz Wacława Sierpińskiego. In: Portrety uczonych. Profesorowie Uniwersytetu Warszawskiego 1816–1915. Eds. M. Wąsowicz, A.K. Wróblewski. Warszawa: Wydawnictwa Uniwersytetu Warszawskiego, p. 491.
• Schumann A.H., 1998, Thiessen polygon. In: Encyclopedia of Hydrology and Lakes, “Encyclopedia of Earth Science”. Dordrecht: Springer, pp. 648–649.
• Sen P.Z., 2009, Spatial modeling principles in earth sciences. Springer, pp. 52–54.
• Serwecińska M., 2014, Diagramy Voronoi. Letnia Szkoła Matematyki. Uniwersytet Śląski. http://www.math. us.edu.pl/lsim2014/MSerwecinska-lsim2014.pdf
• Sierpiński W., 1908, Georgij Woronoj. Streszczenie wykładu, wypowiedzianego na Uniwersytecie Lwowskim dnia 23 listopada 1908 r. In: Portrety uczonych. Profesorowie Uniwersytetu Warszawskiego 1816–1915. Eds. M. Wąsowicz, A.K. Wróblewski. Warszawa: Wydawnictwa Uniwersytetu Warszawskiego, pp. 484–490.
• Syta H. 2010, Short biography of G. Voronoi. http://voronuy.at.ua/publ/statti_anglijska_mova/short_biography_of_g_voronoi_p1/4-1-0-49
• Syta H. 2001, The scientific legacy of Georgii Voronoi and contemporary science. In: Mathematics and the mathematical sciences in Ukraine in the twentieth century (Natsional. Akad. Nauk Ukrainy Inst. Mat., Kiev – 2001), pp. 89–94.
• Szewczuk J., 1977. Sieć zmienogęsta nieregularna, „Polski Przegląd Kartograficzny” Vol. 9, no. 1, pp. 1–12.
• Thiessen A., 1911, Precipitation averages for large areas. “Monthly Weather Review” Vol. 39, no. 7, pp. 1082–1089.
• Ulmer A., 2016, Dzieje Politechniki Warszawskiej w zarysie. „Maszyny Elektryczne – Zeszyty Problemowe” Vol. 4(112), pp. 193–199.
• Urbański J., 2008, GIS w badaniach przyrodniczych. Gdańsk: Wydawnictwo Uniwersytetu Gdańskiego, p. 53.
• van der Putte T., 2009, Using the discrete 3D Voronoi diagram for the modelling of 3D continuous information in geosciences. Master Thesis, Geographical Information Management and Applications. Utrecht University in Geographical Information Management and Applications. http://www.gdmc.nl/publications/2009/3D_Voronoi_diagram.pdf
• Voronoi G., 1908, Nouvelles applications des paramètres continus à la théorie de formes quadratiques. „Journal für die Reine und Angewandte Mathematik” Vol. 134, pp. 198–287.
• Wang S., Rong J., Yang Z., 2014, Transit traffic analysis zone delineating method based on Thiessen polygon. “Sustainability” Vol. 6, no. 4, pp. 1821–1832. DOI: 10.3390/su6041821
• Wu H., Takahashi S., Lin C., Yen H., 2013, Voronoi-based label placement for metro maps. In: 17th International Conference on Information Visualization. London 2013, pp. 96–101. DOI: 10.1109/IV.2013.11
• Xu Y., Fan X.H., Liu K.G., Shi L., Xu. B., Wang F.M., Lin J.P., 2013, Applying and practicing of MATLAB programing for Voronoi tessellation. “Advanced Materials Research” Vol. 706–708, pp. 391–394.