VO+PS "Computational Geometry"

This WWW page is the homepage of my course VO+PS "Computational Geometry" (AISP)/"Algorithmische Geometrie". 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 data structures and algorithms for solving real-world problems.

• PS: FR 11:00-12:00 in T03;
  VO: FR 12:15-14:15 in T03.
• The course will be given (in a slightly blocked manner) at the times specified.
• Both VO and PS will start on 04-Oct-2024 at the time of PS.
• 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:
  • Lecture slides (with all animations and partial build of pages)
  • Study slides (with only a few animations and no partial builds)
  • Printer-friendly slides ("color-reduced" version of the study slides)
  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 undergrad 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 material.
  • Alternatively, you may want to check my lecture slides on
    • Propositional and Predicate Logic,
    • Discrete Mathematics,
    • Geometric Computing,
    • Advanced Algorithms and Data Structures.
    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 lots of assignments out there that are far more challenging and theoretically intricate. 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 so far.
  
  
  
• Computational Geometry Pages (Community effort, maintained by Monique Teillaud and hosted at INRIA).

Copyright © 2025 Martin Held, held@cs.plus.ac.at. All rights reserved. Impressum and Disclaimer. file last modified: Tuesday, 23-Sep-2025 15:45:39 CEST