50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Computational Geometry - CS3702


Veranstaltungsart und -inhalt
Titel Computational Geometry
Dozent Prof. Dr. Maciej Liskiewicz
Einordnung Bachelor-Studiengang Informatik 5. Semester, in englischer Sprache
Inhalte 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 hull constructions, finding the shortest paths with applications to robot motion planning, testing intersections of lines, triangulation, Voronoi diagrams, visibility problems, etc.

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 (for more examples see e.g. http://www.Voronoi.com/).

Empfohlene Literatur
  • M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer, 2. rev.ed., 2000
  • J. O'Rourke, Computational Geometry in C. Cambridge University Press, 1998
  • H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer 1987
  • J.E. Goodman and J. O'Rourke (Eds.), Handbook of Discrete and Computational Geometry

Seminar
Dozent Prof. Dr. Maciej Liskiewicz Benito van der Zander M.Sc.
Umfang 2 SWS, ECTS-Credits: 4, in englischer Sprache
Termine Mo. 10:00-12:00h, Seminarraum ITCS 2021