Computational geometry


Aim of the course

The primary objective is to show students the ways to solve basic problems occurring in computational geometry (such as: search for geometric convexity, proximity, intersection, polygonization, and optimization of geometric objects), and present the achievements of computational geometry which are applied e.g. in reality modelling, computer simulations, computer graphics, cartography, and robotics.

Lecture programme

Introduction: historical background, the ways of representing geometric objects, geometric data structures, basic methods of solving geometrical problems. Geometric search: the problem of the location of point, the scope of search. Convex envelope. Detection of intersections in 2D and 3D. Polygonization of 2D and 3D objects. Problems of visibility, monitoring problems. The search for the nearest neighborhood. Geometric problems of movement of objects. Informatic problems in computational geometry, usage of computational geometry in modelling, computer simulation, graphics, computer games, etc.

Overview of the course elements

As part of the laboratory classes stuedents learn about the implementation of algorithms of computational geometry with different environments, techniques and languages. Gaining skills in solving basic problems that features computational geometry.

Reading list

1. Geometria obliczeniowa. Algorytmy i zastosowania, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf , WNT, 2007
2. Geometria obliczeniowa. Wprowadzenie, F.P. Preparata, M.I. Shamos, Helion, 2003
3. Computational Geometry in C, J. O’Rourke, Cambridge University Press, 2000
4. Geometric Folding Algorithms, E. D. Demaine, J. O’Rourke, Cambridge University Press, 2007
5. Podstawy modelowania krzywych i powierzchni. Zastosowanie w grafice komputerowej, Przemysław Kiciak, WNT 2005

Copyright © 2010 Department of Computer Science   |   AGH University of Science and Technology   |   Created by Creative Bastards