====== Computational Geometry ======

**Lecturer:** [[people:thomasblaesius|]]

**Teaching Assistants:** [[people:vonderheydt|]], [[people:marcuswilhelm|]], [[people:wendyyi|]] 
\\
\\
Spatial data is processed in a wide variety of areas in computer science, such as computer graphics and visualization, geographic information systems, robotics, and more. Computational geometry focuses on the design and analysis of geometric algorithms and data structures. This module introduces frequently used techniques and concepts in computational geometry, which are explored in depth using selected and application-related questions.

See [[https://campus.studium.kit.edu/english/search.php#!campus/all/abstractModuleView.asp?gguid=0x5209947B0865E0428A350951FD46F2EF|here]] for more info.

===== Schedule =====

We meet every week on Mondays at 3:45 PM and Thursdays at 3:45 PM in room 131. The first lecture will take place on Thursday, April 24th, at 3:45 PM.

^     ^ Monday (15:45)                                                                               ^ Thursday (15:45)                                                                       ^ Sheet                                                   ^
| 1   | 22.04.2025 - 🏝 Easter Monday                                                                 | 24.04.2025 - {{ :teaching:2025ss:comput_geom:01-convex-hull.pdf |Lecture 1}}           | {{ :teaching:2025ss:comput_geom:sheet01.pdf |Sheet 1}}  |
| 2   | 28.04.2025 - {{ :teaching:2025ss:comput_geom:02-segment-intersection.pdf |Lecture 2}}        | 01.05.2025 - 🏝 Labour Day                                                              |                                                         |
| 3   | 05.05.2025 - {{ :teaching:2025ss:comput_geom:03-polygon-triangulation.pdf |Lecture 3}}       | 08.05.2025 - Exercise 1                                                                |                                                         |
| 4   | 12.05.2025 - {{ :teaching:2025ss:comput_geom:04-lp-half-plane-intersection.pdf |Lecture 4}}  | 15.05.2025 - Active Session 1                                                          | {{ :teaching:2025ss:comput_geom:sheet02.pdf |Sheet 2}}  |
| 5   | 19.05.2025 - {{ :teaching:2025ss:comput_geom:05-range-trees.pdf |Lecture 5}}                 | 22.05.2025 - {{ :teaching:2025ss:comput_geom:06-fractional-cascading.pdf |Lecture 6}}  |                                                         |
| 6   | 26.05.2025 - {{ :teaching:2025ss:comput_geom:exercise02.pdf |Exercise 2}}                    | 29.05.2025 - 🏝 Ascension Day                                                           | {{ :teaching:2025ss:comput_geom:sheet03.pdf |Sheet 3}}      {{:teaching:2025ss:comput_geom:rangetree.zip | RangeTree.zip}}                                            |
| 7   | 02.06.2025 - Lecture 7                                                                       | 05.06.2025 - Exercise 3                                                                |                                                         |
|     | 09.06.2025 - 🏝 No Lecture                                                                    | 12.06.2025 - 🏝 No Lecture                                                              |                                                         |
| 8   | 16.06.2025 - Lecture 8                                                                       | 19.06.2025 - 🏝 Corpus Christi                                                          | Sheet 4                                                 |
| 9   | 23.06.2025 - Lecture 9                                                                       | 26.06.2025 - Exercise 4                                                                |                                                         |
| 10  | 30.06.2025 - Lecture 10                                                                      | 03.07.2025 - Active Session 2                                                          | Sheet 5                                                 |
| 11  | 07.07.2025 - Lecture 11                                                                      | 10.07.2025 - Exercise 5                                                                |                                                         |
| 12  | 14.07.2025 - Lecture 12                                                                      | 17.07.2025 - Active Session 3                                                          | Sheet 6                                                 |
| 13  | 21.07.2025 - Lecture 13                                                                      | 24.07.2025 - Exercise 6                                                                |                                                         |
| 14  | 28.07.2025 - Lecture 14                                                                      | 31.07.2025 - Summary / Active                                                          |                                                         |

===== Lecture =====

  - Convex Hull: {{ :teaching:2025ss:comput_geom:01-convex-hull.pdf |with clicks}}, {{ :teaching:2025ss:comput_geom:01-convex-hull-print.pdf |without clicks}}
  - Line Segment Intersection: {{ :teaching:2025ss:comput_geom:02-segment-intersection.pdf |with clicks}}, {{ :teaching:2025ss:comput_geom:02-segment-intersection-print.pdf |without clicks}}
  - Polygon Triangulation: {{ :teaching:2025ss:comput_geom:03-polygon-triangulation.pdf |with clicks}}, {{ :teaching:2025ss:comput_geom:03-polygon-triangulation-print.pdf |without clicks}}
  - Linear Programs & Half-Plane Intersection: {{ :teaching:2025ss:comput_geom:04-lp-half-plane-intersection.pdf |with clicks}}, {{ :teaching:2025ss:comput_geom:04-lp-half-plane-intersection-print.pdf |without clicks}}
  - Range Trees: {{ :teaching:2025ss:comput_geom:05-range-trees.pdf |with clicks}}, {{ :teaching:2025ss:comput_geom:05-range-trees-print.pdf |without clicks}}
  - Fractional Cascading: {{ :teaching:2025ss:comput_geom:06-fractional-cascading.pdf |with clicks}}, {{ :teaching:2025ss:comput_geom:06-fractional-cascading-print.pdf |without clicks}}
===== Exercises =====

  * {{ :teaching:2025ss:comput_geom:exercise01.pdf | Exercise 1}}, {{ :teaching:2025ss:comput_geom:ex1_discon_geomgraph.pdf |}}
  * {{ :teaching:2025ss:comput_geom:exercise02.pdf |Exercise 2}}
===== Exercise Sheets =====

  * {{ :teaching:2025ss:comput_geom:sheet01.pdf |Sheet 1}}
  * {{ :teaching:2025ss:comput_geom:sheet02.pdf |Sheet 2}}
  * {{ :teaching:2025ss:comput_geom:sheet03.pdf |Sheet 3}} {{:teaching:2025ss:comput_geom:rangetree.zip | RangeTree.zip}}  


===== Additional Materials =====

  * Duality: {{ :teaching:2025ss:comput_geom:01-active-duality.pdf |Slides}}