VO+PS "Computational Geometry"
This WWW page is the home page of
VO+PS "Computational Geometry" (AISP)/"Algorithmische Geometrie" (SS 2020).
Computational geometry is the study of the design and analysis of efficient
algorithms for solving problems with a geometric flavor. The
methodologies of computational geometry allow one to investigate solutions
of numerous geometric problems that arise in application
areas such as computer-aided design, manufacturing, geographic information
systems, image processing, robotics and graphics.
This course offers a graduate-level
introduction to computational
geometry: We will discuss geometric searching, convex hulls, Voronoi
diagrams, straight skeletons, triangulations, and robustness issues. We will
learn to analyze geometric problems and to design algorithms
for solving them in an efficient manner. Students will be exposed to important
algorithmic paradigms of geometric computing, and will acquire in-depth
knowledge of basic geometric data structures (such as triangulations and
Voronoi diagrams). This course will also cover sample applications of these
structures and algorithms for solving real-world problems.
- PS: FR 10:15-11:15 in T02;
VO: FR 11:30-13:30 in T02.
- The course will be given (in a slightly blocked manner) at the times
- Both VO and PS will start on 06-March-2020 at the time of PS.
- Changes due to COVID-19 pandemia [Wed 18-March-2020 08:45]:
- All lectures (VO) will be conducted by means of Google's video conference
system Hangouts Meet at the PLUS channel
- All proseminar (PS) sessions will be conducted by means of Google's video
conference system Hangouts Meet at the PLUS channel
- Please make sure to log in with your standard (University)
account. Don't use any private GMail account or the like!
- All online sessions will take place exactly during the times scheduled
for the original classroom-based events.
- Both VO and PS will be taught in English if foreign
(AISP) students who are not fluent in German decide to take the course. (I will
also take questions in German, though.)
- The slides used in the VO lectures are available as PDF files:
All three versions are updated consistently by means of a script. (Please
let me know if you'd catch a problem that might be due to this automated
generation of these PDF files.)
- Please note that a standard knowledge of (discrete) mathematics,
algorithms and data structures, complexity theory and geometric computing
will be required to take the course!
- Please consult appropriate textbooks if you feel uneasy with that
- Alternatively, you may want to check my lecture slides on
Yes, these slides all are in English!
Grading policy for VO and PS.
Homework assignments for the PS.
- As a final remark, let me emphasize that the level of theoretical
difficulty of the contents of the VO and of the PS assignments will be
rather moderate compared to international standards. Take a look at some
of the leading textbooks, or grab assignments posted by colleagues on the
web, and you'll quickly learn that there are far more involved
assignments out there. I appreciate the fact, though, that this type
of work (and the skills required) are set apart from most of the other
classes that you might have attended in your CS (or even math) studies
Computational Geometry Pages (Community effort, maintained by
Monique Teillaud and hosted at INRIA).