Type and Content

The subject of computational geometry is to develop efficient methods for representing and manipulating geometric objects. These kinds of problems occur in several academic and applied areas of computer science like computer graphics, robotics, molecular biology, CAD/CAM, and geographic information systems. Within the talks of this seminar we will focus ourselves on the basic problems of computational geometry and discuss several data structures and algorithms providing efficient solutions to the problems. The presented solutions are both easy to implement and understand. Some of the discussed problems are: convex hulls, finding the shortest paths with applications to robot motion planning, testing intersections of lines, triangulation, Voronoi diagrams, and visibility problems.

An interesting aspect of computational geometry is that some applications seem to be only slightly connected to geometry. E.g. Voronoi diagrams, the canonical problem of computational geometry, have applications in areas like archaeology, chemistry, biology, and many others (often known under different names). Some of them can be found in the internet (http://www.Voronoi.com/).

• F. Preparata, M. Shamos, Introduction to Computational Geometry, Springer 1985
• H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer 1987
• M. de Berg, M.V. Kreveld, M.Overmars, O. Schwarzkopf, Computational Geometry, Springer 1997
• J. O'Rourke, Computational Geometry in C. Cambridge University Press, 1999