Computational Geometry

This e-learning text was originally written in Czech for the students of the course Geometric algorithms which has been running at the Faculty of Science and the Faculty of Informatics of the Masaryk University since the mid-1990s. At that time, computational geometry was a new field, and its first textbooks had just begun to appear. One of them was the book Computational Geometry, Algorithms and Applications by de Berg, van Krevelda, Overmarse, and Schwarzkopf published by Springer in 1997. The book quickly met the second (2000) and third editions (2008). The authors of the third edition are de Berg, Cheong, van Kreveld and Overmars. The topics and algorithms from the first half of this book are the content of the presented text.

The text is written with maximum effort for simplicity, clarity and shortness. It is accompanied by a large number of pictures and animations to illustrate the introduced concepts and algorithms. Emphasis is placed on the ideas of algorithms, these are explained and illustrated before pseudocodes are described. Pseudocodes of algorithms with the exception of Chapter 5 are taken from the above book. Several pictures in chapters 2 and 3 are also taken from the same source. However, most pictures and all animations are original. This text cannot, of course, replace the book. In the book, the reader finds motivation for each main algorithm at the beginning of the chapter and its several applications at the end which are missing in the presented text. In it at the end of several chapters the reader can find references to bachelor and diploma theses of my students which provide details of algorithms, eventually also their implementations.

In 2017, the course Geometric algorithm began to be taught in English. In this context, this English version of e-learning has emerged. During the translation into English several parts of the text have been rewritten and many mistakes have been corrected. I am gratefull to Bc. Tadeáš Kučera for reading the text and improving and correcting it. The remaning gaps and mistakes are only my responsibility and I ask the reader to alert me of them by the email to the address cadek@math.muni.cz.

The realization of the text as an e-learning is the work of the staff of the e-Learning Service Center at the Masaryk University. I am especially gratefull to Mr. Jiří Boček for his carefullness and patience.

Martin Čadek

Print

Skripta ke stažení se připravují

Author

	doc. RNDr. Martin Čadek, CSc. Ústav matematiky a statistiky, Přírodovědecká fakulta MU Osobní stránka v IS MU