50 years Univerity of Lübeck

Institute for Theoretical Computer Science

WS 2005/2006 – Computational Geometry



Type and Content

Title: Computational Geometry
Host: Liskiewicz
Classification: Bachelor-Studiengang ab 1. Semester, Wahlpflicht
Diplom-Studiengang ab 1. Semester, Wahl
Proseminar in englischer Sprache, 4 ECTS
Dates: Mi 14h – 16h, Seminarraum Informatik 1 (Gödel)
Conentent:

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/).

Literature:
  • 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