Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Computational Geometry (251-1425-00L) HS11

 

Time & Place

Lecture: Monday 13:15-15:00 CAB G51 and Thursday 13:15-14:00 CHN G 46. The lecturers are:
Bernd Gärtner, CAB G32.2, Tel: 044 632 70 26, .
Michael Hoffmann, CAB G33.1, Tel: 044 632 73 90, .
Exercise: Thursday 14:15-16:00, CHN G46 . The teaching assistant is:
Tobias Christ, CAB J21.2, Tel: +41-44-632 75 49, .
 

Contents

 

Course Material

Date Content Exercises Lecture notes and links
#1 Thursday 22.09.2011 Information about the course, applications of geometry Exercise 1 Introductory Slides
#2 Monday 26.09.2011 Convex Hull 2.12, 2.13, 2.14, and 2.18 Lecture Notes
#3 Thursday 29.09.2011 Chan's Algorithm Homework 1
#4 Monday 03.10.2011 Line Sweep 3.7, 3.13, 3.14, 3.17 Lecture Notes
#5 Thursday 06.10.2011 Red-Blue Intersections
#6 Monday 10.10.2011 Plane Graphs, DCEL, Triangulations 4.2, 4.3, 4.7, 4.12 Lecture Notes
#7 Thursday 13.10.2011 Delaunay Triangulation, Lawson Flips
#8 Monday 17.10.2011 Delaunay Graph, Incremental Construction 5.12, 5.13, 6.4 Lecture Notes
#9 Thursday 20.10.2011 Randomized Incremental Construction Homework 2 Lecture Notes
#10 Monday 24.10.2011 Trapezoidal Maps 8.17 Lecture Notes
#11 Thursday 27.10.2011 Trapezoidal Maps (cont.)
#12 Monday 31.10.2011 Voronoi Diagrams 9.2, 9.15, 9.22, 9.23 Lecture Notes
#13 Thursday 03.11.2011 Kirkpatrick's Hierarchy Homework 3
Solutions to HW3
#14 Monday 07.11.2011 Linear Programming, Seidel's algorithm 10.5, 10.6 Lecture Notes
#15 Thursday 10.11.2011 Seidel's algorithm
#16 Monday 14.11.2011 Linear Programming: Randomized Algorithm; Smallest Enclosing Balls 11.8, 12.6 Lecture Notes
#17 Thursday 17.11.2011 Lecture Notes
#18 Monday 21.11.2011 Line Arrangements 14.3, 14.6, 14.9 Lecture Notes
#19 Thursday 24.11.2011 Segment Endpoint Visibility Graphs Homework 4
Solutions to HW4		 s.a.
#20 Monday 28.11.2011 Ham-Sandwich Cuts 14.18, 14.19, 14.21 s.a.
#21 Thursday 01.12.2011 3-Sum s.a.
#22 Monday 05.12.2011 Davenport-Schinzel Sequences 15.5, 15.6, 15.8, 15.12 Lecture Notes
#23 Thursday 08.12.2011 Complexity of a single cell in an arrangement of Jordan arcs s.a.
#24 Monday 12.12.2011 Epsilon nets 16.4, 16.5 Lecture Notes
#25 Thursday 15.12.2011
#26 Monday 19.12.2011
#27 Thursday 22.12.2011
 

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 assitant. 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).

In Addition, you receive four homeworks during the semester. The homeworks are to be solved in written form and typically you have two weeks of time to return your solutions/reports, typeset in LaTeX. In contrast to the exercises, they do count towards the final grade: Your three best grades will account for 10% of your final grade each. Solving the homework in teams is not allowed. Besides one or two exercises, the homework may include a small research project, or you are asked to give a short talk about your last small research project.

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 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 special exercises 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 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