252-1425-00L  Geometry: Combinatorics and Algorithms

SemesterAutumn Semester 2022
LecturersB. Gärtner, E. Welzl, M. Hoffmann
Periodicityyearly recurring course
Language of instructionEnglish



Courses

NumberTitleHoursLecturers
252-1425-00 VGeometry: Combinatorics and Algorithms3 hrs
Mon13:15-14:00CAB G 51 »
Thu14:15-16:00CAB G 51 »
05.12.14:15-18:00ML H 37.1 »
14:15-18:00ML H 43 »
06.12.14:15-18:00ML H 37.1 »
B. Gärtner, E. Welzl, M. Hoffmann
252-1425-00 UGeometry: Combinatorics and Algorithms2 hrs
Mon14:15-16:00CAB G 51 »
Tue14:15-16:00CAB H 52 »
B. Gärtner, E. Welzl, M. Hoffmann
252-1425-00 AGeometry: Combinatorics and Algorithms
Project Work, no fixed presence required.
2 hrsB. Gärtner, E. Welzl, M. Hoffmann

Catalogue data

AbstractGeometric 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?)
ObjectiveThe 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.
ContentPlanar 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.
Lecture notesyes
LiteratureMark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong, Computational Geometry: Algorithms and Applications, Springer, 3rd ed., 2008.
Satyan Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.
Stefan Felsner, Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry, Teubner, 2004.
Jiri Matousek, Lectures on Discrete Geometry, Springer, 2002.
Takao Nishizeki, Md. Saidur Rahman, Planar Graph Drawing, World Scientific, 2004.
Prerequisites / NoticePrerequisites: The course assumes basic knowledge of discrete mathematics and algorithms, as supplied in the first semesters of Bachelor Studies at ETH.
Outlook: In the following spring semester there is a seminar "Geometry: Combinatorics and Algorithms" that builds on this course. There are ample possibilities for Semester-, Bachelor- and Master Thesis projects in the area.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits8 credits
ExaminersM. Hoffmann, B. Gärtner, E. Welzl
Typesession examination
Language of examinationEnglish
RepetitionThe performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examinationoral 30 minutes
Additional information on mode of examination60% final oral exam: 30 minutes oral exam with 30 minutes preparation time (no material allowed) plus two graded homework (20% each). The two mandatory graded homework (compulsory continuous performance assessments) will be released throughout the semester, at specific dates that will be announced. Each graded homework will have a deadline two weeks after the release.
The solutions must be typeset in LaTeX (or similar).
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

 
Main linkCourse Homepage
Only public learning materials are listed.

Groups

No information on groups available.

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
CAS in Computer ScienceFocus Courses and ElectivesWInformation
Cyber Security MasterCore CoursesWInformation
Computer Science MasterCore CoursesWInformation
Computer Science MasterMinor in Theoretical Computer ScienceWInformation
Mathematics BachelorAuswahl: Theoretical Computer ScienceWInformation
Mathematics MasterSelection: Theoretical Computer Science, Discrete MathematicsWInformation