Ab 2. November 2020 findet das Herbstsemester 2020 online statt. Ausnahmen: Veranstaltungen, die nur mit Präsenz vor Ort durchführbar sind. Bitte beachten Sie die per E-Mail kommunizierten Informationen der Dozierenden.

252-1425-00L  Geometry: Combinatorics and Algorithms

SemesterHerbstsemester 2018
DozierendeE. Welzl, L. F. Barba Flores, M. Hoffmann
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheEnglisch



Katalogdaten

KurzbeschreibungGeometric 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?)
LernzielThe 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.
InhaltPlanar 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.
Skriptyes
LiteraturMark 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.
Voraussetzungen / BesonderesPrerequisites: 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.

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte6 KP
PrüfendeM. Hoffmann, L. F. Barba Flores, E. Welzl
FormSessionsprüfung
PrüfungsspracheEnglisch
RepetitionDie Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Prüfungsmodusmündlich 30 Minuten
Zusatzinformation zum Prüfungsmodus70% final oral exam: 30 minutes oral exam with 30 minutes preparation time (no material allowed).
30% project work (compulsory continuous performance assessment): At times during the semester, we hand out specially marked projects. The written part of the solutions are expected typeset in LaTeX or similar. Solutions are graded, and the best three grades will account for 10% of the final grade each. Projects can be discussed with colleagues, but we expect an independent writeup.
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.

Lernmaterialien

 
HauptlinkCourse Homepage
Es werden nur die öffentlichen Lernmaterialien aufgeführt.

Lehrveranstaltungen

NummerTitelUmfangDozierende
252-1425-00 VGeometry: Combinatorics and Algorithms2 Std.
Do13-15CAB G 51 »
E. Welzl, L. F. Barba Flores, M. Hoffmann
252-1425-00 UGeometry: Combinatorics and Algorithms2 Std.
Do15-17ML H 41.1 »
E. Welzl, L. F. Barba Flores, M. Hoffmann
252-1425-00 AGeometry: Combinatorics and Algorithms
Project Work, no fixed presence required.
1 Std.E. Welzl, L. F. Barba Flores, M. Hoffmann

Gruppen

Keine Informationen zu Gruppen vorhanden.

Einschränkungen

Keine zusätzlichen Belegungseinschränkungen vorhanden.

Angeboten in

StudiengangBereichTyp
CAS in InformatikFokusfächer und WahlfächerWInformation
Doktorat Departement InformatikLehrangebot Doktorat und PostdoktoratWInformation
Informatik MasterWahlfächer der Vertiefung in Theoretical Computer ScienceWInformation
Informatik MasterWahlfächer der Vertiefung General StudiesWInformation
Mathematik BachelorAuswahl: Theoretische InformatikWInformation
Mathematik MasterAuswahl: Theoretische Informatik, diskrete MathematikWInformation