---

Time & Place

Lecture: Monday 13:15-15:00 CAB G59 and Thursday 13:15-14:00 CAB G51. The lecturers are:
Exercise: Thursday 14:15-16:00, CAB G51. The teaching assistant is:

Contents

• Course material
• Course description
• Procedures, exercises, exam
• Complementary courses
• Further literature and links

Course Material

Information about the course, applications of geometryConvex Hull

Date	Content	Exercises	Lecture notes and links
#1 (17.9.2009)	Exercise 1
#2 (21.9.2009)	Exercise 2	Lecture 1
#3 (24.9.2009)	Faster convex hull (Chan's algorithm)		Lecture 2
#3 (28.9.2009)	Triangulations	Exercise 3	Lecture 3
#4 (1.10.2009)	Triangulations of Convex Polygons - A Historical Note (by Emo Welzl)	Homework 1
#5 (5.10.2009)	Delaunay Triangulations	Exercise 4	Lecture 4
#6 (8.10.2009)	Incremental Construction of the Delaunay Triangulation		Lecture 5
#7 (12.10.2009)	Randomized Incremental Construction (RIC); Voronoi Diagrams	Exercise 5	Slides (RIC), Lecture 6
#8 (15.10.2009)	Kirkpatrick's hierarchy	Homework 2	Lecture 7
#9 (19.10.2009)	Randomized Incremental Construction (RIC), Part II; Trapezoidal map	Exercise 6	Lecture 8, Slides (trapezoidal map)
#10 (22.10.2009)	Triangulating a Simple Polygon with Fast Trapezoidal Maps		Slides (trapezoidal map)
#11 (26.10.2009)	Line Segment Intersections	Exercise 7	Lecture 9
#12 (29.10.2009)	Randomized incremental construction of line segment intersections
#13 (2.11.2009)	Line Arrangements	Exercise 8	Lecture 10
#14 (5.11.2009)	Computing Ham-Sandwich Cuts in 2D	Homework 3	Lecture 11
#15 (9.11.2009)	Visibility Graphs and 3-Sum		Lecture 12
#16 (12.11.2009)	Linear Programming	Exercise 9	Lecture 13
#17 (16.11.2009)	Linear Programming: A Randomized Algorithm	Exercise 10	Lecture 14
#18 (19.11.2009)	Linear Programming: A Randomized Algorithm II		Lecture 15
#19 (23.11.2009)	Smallest Enclosing Balls - Basics	Exercise 11	Lecture 16
#20 (26.11.2009)	Smallest Enclosing Balls - Swiss Algorithm	Homework 4	Lecture 17
#21 (30.11.2009)	Davenport-Schinzel Sequences	Exercise 12	Lecture 18
#22 (3.12.2009)	Translational Motion Planning		Lecture 19
#23 (7.12.2009)	Pseudotriangulations	Exercise 13	Lecture 20
#24 (10.12.2009)
#25 (14.12.2009)	Range Trees		Lecture 22
#26 (17.12.2009)

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 addresses basic geometric data structures and 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, Delaunay triangulations, Voronoi diagrams, arrangements, point location, range, segment and interval trees, smallest enclosing balls, hard geometric problems, and curve reconstruction.

Procedures, exercises, exam

Every week we provide you with an exercise sheet. You should solve it in written form and return your solutions the week after. Your solutions are thoroughly commented and graded, 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 :-)).

In Addition, you receive four small projects during the semester. Also these projects are to be solved in written form, but typically you have two weeks of time to return your solutions/reports, typeset in LaTeX. In contrast to the exercises, projects do count towards the final grade: Your three best grades will account for 10% of your final grade each. Solving projects in teams is not allowed.

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 projects.

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 following rule applies for obtaining credit points (KE) for the course. If you successfully solve (grade 4.0 or better) three out of the four special exercises you get a "Testat" and 5KE. In order to obtain the remaining 3 KE, you have to take and pass the final exam. No credit points are given for simply sitting in the course.

Complementary Courses & Semester/Master/Diploma Theses

This course is complemented by a seminar that takes place every spring semester. Furthermore, after  having completed 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.

Literature and Links

• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry: Algorithms and Applications, Springer, 3rd edition, 2008.
• Franco P. Preparata, Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985.
• Bernds Skript for a course held in Berlin in 1996
• New to LaTex? Look at Tobias Oetiker's Not So Short Introduction to LaTeX.
• No idea how to run LaTex on your Window Computer? The usual (La)TeX distribution for Windows is MiKTeX

---