# Computational Geometry (252-1425-00L) HS12

## Time & Place

Lecture: Monday 13:15-15:00, CAB G51 and Thursday 13:15-14:00, CAB G51. The lecturers are:
Bernd Gärtner, CAB G31.1, Tel: 044 632 70 26, .
Michael Hoffmann, CAB G33.1, Tel: 044 632 73 90, .
Exercise: Thursday 14:15-16:00, CAB G51. The teaching assistant is:
Anna Gundert, CAB G19.2, Tel: +41-44-633 32 22, .

## Course Material

Complete Lecture Notes - UPDATED on 15.1.2013
 Date Content Exercises Lecture notes, homeworks and links #1 Thursday 20.09.2012 Information about the course, applications of geometry Exercise 1 Introductory Slides #2 Monday 24.09.2012 Fundamentals, Polygons Lecture Notes - Chapters 1 and 2 #3 Thursday 27.09.2012 Polygons, Triangulations, Art Gallery Problem 2.2, 2.3, 2.4, 2.6, 2.10, 2.11, 2.16, 2.17, 2.19, 2.20 Lecture Notes - Chapters 1 and 2 - UPDATED on 28.09.2012 #4 Monday 01.10.2012 Convex Sets, Convex Hull Lecture Notes - Chapter 3 #5 Thursday 04.10.2012 Convex Hull 3.9, 3.11, 3.12, 3.14, 3.18, 3.20 #6 Monday 08.10.2012 Line Sweep, Segment Intersections Lecture Notes - Chapter 4 - UPDATED on 10.10.2012 #7 Thursday 11.10.2012 Red-Blue Intersections 3.19, 4.11, 4.12, 4.14, 4.16 Homework 1 #8 Monday 15.10.2012 Plane Graphs, DCEL Lecture Notes #9 Thursday 18.10.2012 Triangulation of a Point Set, Delaunay Triangulation, Lawson Flips 4.17, 5.2, 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 6.6, 6.7, 6.12 Lecture Notes #10 Monday 22.10.2012 Delaunay Graph #11 Thursday 25.10.2012 Constrained Delaunay Triangulation, Incremental Construction 6.15 Lecture Notes #12 Monday 29.10.2012 Randomized Incremental Construction Lecture Notes #13 Thursday 01.11.2012 Randomized Incremental Construction (cont.) 7.4, 8.7 Homework 2 On Exercise 3: The talks will take place on the 29th of November, during the exercise session. #14 Monday 05.11.2012 Trapezoidal Maps Lecture Notes #15 Thursday 08.11.2012 Trapezoidal Maps (cont.) 9.23 #16 Monday 12.11.2012 Voronoi Diagrams Lecture Notes #17 Thursday 15.11.2012 Kirkpatrick's Hierarchy 10.2,10.15,10.24,10.25,10.26 #18 Monday 19.11.2012 Linear Programming, Seidel's algorithm Lecture Notes #19 Thursday 22.11.2012 Seidel's algorithm (cont.) Trial Talks Homework 3 #20 Monday 26.11.2012 Seidel's algorithm (cont.), Line Arrangements, Zone Theorem Lecture Notes #21 Thursday 29.11.2012 Minimum Area Triangle, Visibility Graphs Presentations for HW 2! #22 Monday 03.12.2012 Ham-Sandwich Cuts, 3-Sum #23 Thursday 06.12.2012 Davenport-Schinzel Sequences 13.2,13.3,13.4,13.6 Lecture Notes #24 Monday 10.12.2012 Epsilon nets Lecture Notes #25 Thursday 13.12.2012 Extra exercise session 14.5, 14.6, 14.7, 14.8, 14.9, 15.5 #26 Monday 19.12.2011 Epsilon nets #27 Thursday 22.12.2011 Epsilon nets

## Course Description

Computational Geometry is about design and analysis of efficient algorithms for geometric problems, typically in low dimensions (2,3,..). These are needed in many application domains, such as geographic information systems, computer graphics, or geometric modeling. The lecture introduces important design paradigms for geometric algorithms. Its goal is to make students familiar with the important techniques and results in computational geometry, and to enable them to attack theoretical and practical problems in various application domains.

Covered topics include convex hulls, line sweep algorithms, Delaunay triangulation, randomized incremental constructions, trapezoidal decomposition, Voronoi diagrams, pesudotriangulation, linear programming, smallest enclosing balls, arrangements, Davenport-Schinzel sequences, motion planning, and epsilon nets.

## Procedures, Exercises, Exam

Every week we provide you with exercises. You should solve them in written form and you are encouraged to hand in your solutions to the teaching assistant. Your solutions are thoroughly commented, but they do not count towards your final grade. The motivation to work on the exercises stems from your interest in the topic (and possibly also the desire to succeed in the exam).

There is an oral exam of 30 minutes during the examination period. Your final grade consists to 70% of the grade for the exam and to 30% of the grade for the homework assignments.

You are expected to learn proofs discussed in the lecture, should be able to explain their basic ideas and reproduce more details on demand. You should also be able to give a short presentation on any topic treated throughout the course.

One of the questions given to you during the exam is to solve one of the exercises posed throughout the semester.

Roughly half an hour before the exam you get to know the exercise to be solved and one topic that you will be questioned about in particular, that is, you have 30 minutes preparation time. For this preparation, paper and pencil will be provided. You may not use any other material, like books or notes.

For PhD students, the same rules apply for obtaining credit points as for all other participants. Taking the exam and achieving an overall grade of at least 4.0 (computed as a weighted average of grades for homework and the written final exam as detailed above) qualifies for receiving credits. In order to comply with new regulations recently issued by the department, merely attending the course and/or handing in exercises is no longer sufficient.

## Complementary Courses & Semester/Master/Diploma Theses

This course is complemented by the seminar Computational Geometry and Graph Drawing which also runs this semester. After having completed both the course and the seminar, it is possible to do a semester, master or diploma thesis in the area of Computational Geometry. Students are also welcome at our graduate seminar.