Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl
Institut für Theoretische Informatik
Departement Informatik
ETH Zürich
CH–8092 Zürich
phone | +41–44–632 73 92 |
fax | +41–44–632 10 63 |
(ETH Zurich Postdoctoral Fellowship.) The main objective of this project is to discover new fundamental results in the area of computational geometry from a theoretical point of view. We study dynamic data structures and algorithms motivated by the problem of having constantly changing objects in geometric spaces. Preprocessing is crucial to obtain a good query performance, either by independently preprocessing each object, or by a general data structure that captures the proximity information of all the objects (such as Voronoi diagrams). In this setting, we aim to study the following general problem: Given a collection of objects in a geometric space that are changing over time, detect or predict interactions between them or minimize a function defined on them. This general problem depends on several parameters and the result of modifying them is a large collection of related problems that can be tackled with similar sets of tools. If we work with a collection of hyperplanes, we obtain problems like the celebrated dynamic convex hull or dynamic linear programming. If each object is a moving convex polyhedron, we can turn to intersection testing and collision detection. Other variants include fundamental problems such as dynamic Voronoi diagrams and dynamic structures for nearest-neighbors, half-emptiness or linear programming queries. The problems in this collection draw their motivation from geographical information systems, motion planning, robotics, computer graphics or simulation, but are on their own fundamental theoretical questions. While efficient algorithms and data structures exist for some of the problems mentioned above, the vast majority assume that objects are static. In reality however, information is constantly being modified and data structures need to be adapted to deal with this fact. Designing geometric data structures for these problems on constantly changing data is a challenging task and the ultimate goal of this project.
Contact: L. Barba.
Duration: Sep 2016 – Aug 2018.
(Erwin Schrödinger Fellowship, Financed by the Austrian Science Foundation (FWF).) For problems like counting geometric graphs on point sets, we are usually not interested in the exact position of the points, but how they are placed relative to each other. The “order type” of a point set tells us in which order we encounter three points of the set when walking along the boundary of the triangle defined by these points in counterclockwise direction. In previous work, we defined a relation on order types by comparing the set of crossing-free geometric graphs each order type admits. We plan to obtain relations between order types that provide more insight into the structure of maximizing and minimizing point sets. In particular, we are interested in bounding the number of triangulations. We will attempt to prove a long-standing conjecture stating that the number of triangulations is minimized by a certain order type, using the insights obtained from different relations and local transformations. Apart from bounding the number of geometric graphs, we are interested in relations between different order types in its own right.
Contact: A. Pilz.
Duration: Mar 2016 – Mar 2019.
(Hasler-Stiftung, D–INFK.) Ein grundlegendes informatisches Wissen ist in unserer Informationsgesellschaft für fast alle Berufe unabdingbar. Um Informationstechnologie nicht nur konsumieren, sondern mitgestalten zu können, sind fundierte Informatikkenntnisse erforderlich. Gleichzeitig steckt die wirkliche Informatik als Fach in den allgemeinbildenden Schulen noch in den Kinderschuhen. Es gibt daher einen grossen Bedarf nach mehr informatischer Bildung in der Schule.
Seit 2015 hat das Kinderlabor im Pilotprojekt Programmieren von klein auf an der ETH ein hochwertiges Bildungsangebot aufgebaut, um Kindern zwischen 4 und 8 Jahren eine altersgerechte Einführung in die Informatik zu ermöglichen. Strategisches Ziel ist es, dazu beizutragen, die Informatik als allgemeinbildendes Fach zu etablieren, das vom Kindergarten bis zur Matur gelehrt wird und dabei Jungen und Mädchen gleichermassen anspricht. Die Rückmeldungen der Lehrpersonen aus dem Pilotprojekt zeigen erfreulich gute Resultate und ein hohes Potenzial, das aber erst noch ausgeschöpft werden muss. Ziele des geplanten Projekts sind deshalb die folgenden:
Damit wird erreicht, dass Mädchen und Jungen schweizweit früh mit Informatik bekannt gemacht werden und die Chance erhalten, ihre Begeisterung für dieses Fach zu entdecken. Lehrpersonen erfahren die Informatik als spannende Disziplin, erhalten einfachen Zugang zu grundlegenden informatischen Denkweisen und können diese an die Kinder weitergeben. Wirtschaft und Hochschulen in der gesamten Schweiz profitieren langfristig von besser qualifizierten Schulabsolventen.
Contact: B. Gärtner.
Duration: Jun 2017 – May 2020