## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Geometry: Combinatorics & Algorithms HS14 - course at ETH Zurich

# Geometry: Combinatorics & Algorithms (252-1425-00L) HS14

## Time & Place

Lecture: Thursday 13:15-15: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, .
Emo Welzl, CAB G39.2, Tel: 044 632 73 70, .
Exercise: Thursday 15:15-17:00, ML H 41.1. The teaching assistant is:
Hemant Tyagi, CAB G19.2, Tel: +41-44-632 77 96, .

## Course Material

Complete Lecture Notes (PDF)
 Date Content Exercises Lecture notes, homeworks and links #1 18.09.2014 Information about the course, planar and geometric graphs 2.3, 2.7, 2.19 Chapters 1,2, Quiz #2 25.09.2014 Unique Embeddings and Combinatorial triangulations 2.8, 2.12, 2.13, 2.14, 2.15, 2.16, 2.27, 2.29 Chapter 2 (cont.) #3 02.10.2014 Compact straight-line drawings 2.34, 2.35 Chapter 2 (cont.), Homework 1, Chapters 1,2 (full) #4 09.10.2014 Polygons, triangulations 3.2, 3.3, 3.4, 3.6, 3.9, 3.13, 3.14, 3.16, 3.17 Chapter 3 (full) #5 16.10.2014 Convex sets, Convex hulls 4.11, 4.13, 4.14, 4.16 Chapter 4 #6 23.10.2014 Convex hulls 4.20, 4.21, 4.22, 4.24 Chapter 4 (cont.), Chapter 4 (full) #7 30.10.2014 Delaunay triangulations 4.25, 5.3, 5.6, 5.7 Chapter 5, Homework 2 #8 06.11.2014 Delaunay triangulations, Incremental construction 5.14 Chapter 5 (cont.), Chapter 5 (full), Chapter 6 (full) #9 13.11.2014 Configuration space framework 6.4 Chapter 7 #10 20.11.2014 Configuration space framework Presentations for HW 2! Chapter 7 (cont.), Chapter 7 (full) #11 27.11.2014 Voronoi diagrams 7.7, 8.2, 8.13, 8.15 Chapter 8 #12 04.12.2014 Voronoi diagrams, Kirkpatrick's Hierarchy, Line arrangements 8.23, 8.24, 8.25, 9.2, 9.3 Chapter 8 (cont.), Chapter 8 (full), Chapter 9 - UPDATED, Homework 3 #13 11.12.2014 Zone Theorem, min. area triangle, rotation systems, 3-Sum 9.4, 9.6, 9.14, 9.15 Chapter 9 (cont.) - UPDATED #14 18.12.2014 Ham Sandwich Theorem 9.20 Chapter 9 (cont.), Chapter 9 (full)

## Course Description

Geometric structures are useful in many areas, and there is a need to understand their structural properties, and to work with them algorithmically. The lecture addresses theoretical foundations concerning geometric structures. Central objects of interest are triangulations. We study combinatorial (Does a certain object exist?) and algorithmic questions (Can we find a certain object efficiently?) Our goal is to make students familiar with fundamental concepts, techniques and results in combinatorial and computational geometry, so as to enable them to model, analyze, and solve theoretical and practical problems in the area and in various application domains. In particular, we want to prepare students for conducting independent research, for instance, within the scope of a thesis project.

Covered topics include: planar and geometric graphs, embeddings and their representation (Whitney's Theorem, canonical orderings, DCEL), polygon triangulations and the art gallery theorem, convexity in R^d, planar convex hull algorithms (Jarvis Wrap, Graham Scan, Chan's Algorithm), point set triangulations, Delaunay triangulations (Lawson flips, lifting map, randomized incremental construction), Voronoi diagrams, the Crossing Lemma and incidence bounds, line arrangements (duality, Zone Theorem, ham-sandwich cuts), 3-SUM hardness, counting planar triangulations.

## 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 a seminar Geometry: Combinatorics & Algorithms in the following spring semester. After having completed the course, it is possible to do a semester, master or diploma thesis in the area. Students are also welcome at our graduate seminar.