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 – August 2018.
(Financed by the Department of Computer Science, ETH Zürich, Haslerstiftung , Akademie der Wissenschaften der Schweiz.) Zusammen mit dem Departement für Informatik der ETH Zurich errichtet das Kinderlabor ein hochqualitatives und gleichzeitig allgemein zugänglichen Weiterbildungsangebot in Informatik. Zielgruppe sind Lehrpersonen in Kindergarten und Unterstufe der Primarschule (1. / 2. Klasse), auch ohne Informatik-Vorkenntnisse. In den Kursen lernen die Teilnehmenden die sogenannten Bee-Bots kennen. Das sind kindlich gestaltete Bodenroboter in Bienenform. Sie können mit vier Richtungstasten so programmiert werden, dass sie vorgegebene Wege laufen können. Zusammen mit den Bee-Bots werden passende Unterrichtsmaterialien vorgestellt und eingesetzt. Nach dem Kurs können Lehrpersonen eine „Bee-Bot-Kiste“ für die Dauer von 2 – 4 Wochen ausleihen. Auf Wunsch kommt ein Studierender der Informatik der ETH Zürich in die Klasse, um die Lehrperson beim Einsatz zu unterstützen und zu coachen.
Contact: B. Gärtner.
Duration: Jan 2015 – Dec 2016.
(Financed by the Swiss National Science Foundation.) Understanding and removing redundancy in a given data to improve computational efficiency or discover its fundamental structure is a universal problem in science and engineering, as the data or the mathematical model to be analyzed in any realistic situation often contains redundant information that is implied by the rest. This research project has two intertwined goals, one of them theoretical, the other one driven by a concrete application. On the theoretical level, we want to understand the structure of redundancy and the complexity of redundancy removal in explicitly or implicitly given linear and more abstract systems. Here we strongly build on our expertise in computational geometry as well as combinatorial optimization. On the application side, we want to compute redundancy and assess the role of redundancy in neuromuscular control, a field that is trying to understand how the nervous system is selecting and implementing specific muscle commands that meet the constraints of specific tasks. This part of the project will be performed in close collaboration with Francisco Valero-Cuevas. He pioneered in modeling the interplay of various muscles in terms of zonotopes whose internal structure determines the possible tasks that the muscles under consideration can achieve together.
Contact: B. Gärtner,
K. Fukuda.
Duration: Oct 2013 – Sep 2016.
(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.
I. Bárány, J. Matoušek, A. Por. Curves in Rd intersecting every hyperplane at most d+1 times. J. European Math. Soc. 18:11 (2016), 2469–2482.
J. Emiris, V. Fisikopoulos, B. Gärtner. Efficient edge-skeleton computation for polytopes defined by oracles. Journal of Symbolic Computation 73:C (2016), 139–152.
B. Gärtner, C. Müller, S. Stich, Variable metric random pursuit. Mathematical Programming, 156:1 (2016), 549-579.
J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner. Untangling two systems of noncrossing curves. Israel Journal of Mathematics 212:1 (2016) 37–79.
H. Tyagi, S. U. Stich, B. Gärtner. On Two Continuum Armed Bandit Problems in High Dimensions. Theory of Computing Systems (TOCS), 58:1 (2016), 191–222.
H. Ahn, L. Barba, E. Oh. The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon. Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), 56:1--56:15.
O. Aichholzer, V. Alvarez, Th. Hackl, A. Pilz, B. Speckmann, B. Vogtenhuber. An Improved Lower Bound on the Minimum Number of Triangulations. Proc. 32nd International Symposium on Computational Geometry (SoCG) (2016), 7:1–7:16.
O. Aichholzer, Th. Hackl, M. Korman, A. Pilz, G. Rote, A. van Renssen, M. Roeloffzen, B. Vogtenhuber. Packing Short Plane Spanning Trees in Complete Geometric Graphs. Proc. 27th International Symposium on Algorithms and Computation (ISAAC) (2016), 9:1–9:12.
O. Aichholzer, V. Kusters, W. Mulzer, A. Pilz, M. Wettstein. An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings. Proc. 26th International Symposium on Algorithms and Computation (ISAAC) (2015), 505–516.
S. Allen, L. Barba, J. Iacono, S. Langerman. Incremental Voronoi diagrams. Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), 15:1–15:16.
C. Annamalai. Finding Perfect Matchings in Bipartite Hypergraphs. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016), 1814–1823.
L. Barba, M. Milatz, J. Nummenpalo, A. Thomas. Deterministic Algorithms for Unique Sink Orientations of Grids. Proc. 22nd International Computing and Combinatorics Conference (COCOON) (2016), 357–369.
S. Fekete, A. Haas, M. Hemmer, M. Hoffmann, I. Kostitsyna, D. Krupke, F. Maurer, J. Mitchell, A. Schmidt, C. Schmidt, J. Troegel, Computing Nonsimple Polygons of Minimum Perimeter, Proc. 15th Symposium on Experimental Algorithms (SEA) (2016), 134-149.
B. Gärtner, A. Krause, A. Kyrillidis, H. Tyagi, Learning Sparse Additive Models with Interactions in High Dimensions, Proc. 19th International Conference on Artificial Intelligence and Statistics (AISTATS) (2016), 111-120.
B. Gärtner, J. Lengler, M. Szedlák. Random Sampling with Removal. 32nd International Symposium on Computational Geometry (SoCG 2016), 40:1–40:16.
B. Gärtner, A. Thomas. The Niceness of Unique Sink Orientations. Proc. 20th International Workshop on Randomization and Computation (APPROX-RANDOM) (2016), 30:1-30:14.
M. Geyer, M. Hoffmann, M. Kaufmann, V. Kusters, C.D. Tóth, The Planar Tree Packing Theorem, Proc. 32nd International Symposium on Computational Geometry (SoCG) (2016), 41:1-41:15.
T. Hertli, I. Hurbain, S. Millius, R. A. Moser, D. Scheder, M. Szedlák. The PPSZ Algorithm for Constraint Satisfaction Problems on More Than Two Colors. Proc. 22nd International Conference on Principles and Practice of Constraint Programming (CP 2016), 412–437.
T. Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas, T. Uno. Approximation and Hardness of Token Swapping. Proc. 24th European Symposium on Algorithms (ESA) (2016), 66:1-66:15.
O. Aichholzer, M. Balko, Th. Hackl, A. Pilz, P. Ramos, P. Valtr, B. Vogtenhuber. Holes in 2-convex point sets. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 263–266.
I. Bárány, K. Buchin, M. Hoffmann, A. Liebenau. An Improved Bound for Orthogeodesic Point Set Embeddings of Trees. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 47–50.
B. Gärtner, J. Lengler, M. Szedlak. Random Sampling with Removal. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 155–158.
C. Huemer, C. Seara, R. I. Silveira, A. Pilz. Production matrices for geometric graphs (extended abstract). Electronic Notes in Discrete Mathematics, 54 (2016), 301–306.
P. Schnider. Packing Plane Spanning Double Stars into Complete Geometric Graphs. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 91–94.
C. ANNAMALAI
Finding Perfect Matchings in Bipartite Hypergraphs.
27th ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington VA, USA (Jan 12, 2016).
L. BARBA
Incremental Voronoi diagrams.
32nd International Symposium on Computational Geometry (SoCG), Boston, USA (Jun 15, 2016).
B. GÄRTNER
Smallest Enclosing Balls In and Out of CGAL.
Perspectives on Geometric Software Design – 20 Years of CGAL, Stels, Switzerland (Sep 10, 2016).
M. HOFFMANN
Orthogeodesic Point Set Embeddings of Trees.
32nd European Workshop on Computational Geometry
(EuroCG), Lugano, Switzerland (Mar 30, 2016).
The Planar Tree Packing Theorem.
32nd International Symposium on Computational Geometry (SoCG), Boston, USA (Jun 14, 2016).
M. MILATZ
Deterministic Algorithms for Unique Sink Orientations of Grids.
22nd International Computing and Combinatorics Conference (COCOON),
Ho Chi Minh City, Vietnam (Aug 3, 2016).
A. N. ZEHMAKAN
Cellular Automata with Majority Rule.
Computer Engineering Seminars, Amirkabir University of Technology, Tehran, Iran (August 1, 2016).
A. PILZ
Deciding monotonicity of complete topological graphs.
Discrete Mathematics Seminar, Technische Universität Berlin, Germany (Nov 30, 2016).
P. SCHNIDER
Packing Plane Spanning Double Stars into Complete Geometric Graphs.
32nd European Workshop on Computational Geometry
(EuroCG), Lugano, Switzerland (Mar 29, 2016).
A. THOMAS
The Niceness of Unique Sink Orientations.
20th International
Workshop on
Randomization and Computation
(APPROX-RANDOM), Paris, France (Sep 09, 2016).
The Niceness of Unique Sink Orientations.
MADALGO Theory Seminar, Aarhus University, Aarhus, Denmark (Sep 20, 2016)
H. TYAGI
Learning Sparse Additive Models with Interactions in High Dimensions.
19th International Conference on Artificial Intelligence and Statistics (AISTATS), Cadiz, Spain (May 11, 2016).
E. WELZL
A Short History of SAT Algorithms.
Symposium on Theoretical Computer Science on the Occasion of Uwe Schöning's 60th Birthday, Univ. Ulm, Villa Eberhardt, Ulm, Germany (Jan 22, 2016).
From Crossing-Free Graphs on Wheel Sets to Polytopes with Few Vertices.
Department of Computer Science,
Tokyo University, Japan (Mar 24, 2016).
From Crossing-Free Graphs on Wheel Sets to Polytopes with Few Vertices.
32nd European Workshop on Computational Geometry (EuroCG), Lugano, Switzerland
(Apr 1, 2016; invited talk).
Embracing Simplices (Simplicial Depth) in a Point Set.
Mittagsseminar Theoretical Computer Science, Berlin Free University,
Berlin, Germany
(May 4, 2016).
Three Lectures on Counting in Geometry – Combinatorics and Algorithms.
Fall School on Discrete Geometry and Topology,
Graz University of Technology, Austria (Oct 5–6, 2016, 7 hours).
M. WETTSTEIN
Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers.
A New Era of Discrete and Computational Geometry, Ascona, Switzerland (Jun 28, 2016).
Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers.
Université Paris-Est Marne-la-Vallée, Paris, France (Dec 6, 2016).
Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers.
École Polytechnique, Paris, France (Dec 7, 2016).
See also the Course Catalogue.
C. ANNAMALAI
Contact assistant Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 16).
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).
L. BARBA
Teaching assistance Diskrete Mathematik (D-INFK) (Fall 16).
K. FUKUDA
Editorial Board Member of
European J. Combinatorics, Computational Geometry: Theory and Applications,
Applied Mathematics Research eXpress.
B. GÄRTNER
Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Mobilitätsberater des Departements Informatik.
Program committee member of
M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Program committee member of
Contact assistant Algorithms Lab (Fall 16).
M. MILATZ
Webmaster www-gremo (since Jul 1).
Teaching assistance Datenstukturen und Algorithmen (D-INFK) (Spring 16).
Contact assistant Algorithms, Probability, and Computing (D-INFK) (Fall 16).
A. N. ZEHMAKAN
Teaching assistance Datenstruktruren und Algorithmen (D-INFK) (Spring 16).
Teaching assistance Algorithmen und Datenstrukturen (D-INFK) (Fall 16).
Teaching assistance Diskrete Mathematik (D-INFK) (Fall 16).
J. NUMMENPALO
Teaching assistance Anwendungsnahes Programmieren mit Matlab (Spring 16).
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).
A. PILZ
Teaching assistance Parallele Programmierung (D-INFK) (Spring 16).
P. SCHNIDER
Contact assistant Geometry: Combinatorics and Algorithms (D-INFK) (Fall 16).
M. SZEDLÁK
Coordinator Mittagsseminar.
Contact assistant Polyhedral Computation (D-MATH) (Spring 16).
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).
A. THOMAS
Topic Coordinator (since Oct 1).
Teaching assistance Datenstruktruren und Algorithmen (D-INFK) (Spring 16).
Teaching assistance Algorithms Lab (D-INFK) (Fall 16).
H. TYAGI
Webmaster www-gremo (until Jun 30).
E. WELZL
Head of department and member of the board of the Department of Computer Science, ETH Zurich (since August 1).
Member of the board (deputy head) of the Department of Computer Science, ETH Zurich (until July 31).
Delegierter für Professorenwahlen an der ETH Zürich.
Coreferee for dissertations of
Editorial/Advisory Board member of
Member (chair, contact person) of selection committees for
Member of the
Program committee member of
M. WETTSTEIN
Teaching assistance coordinator.
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).
Teaching assistance Algorithms Lab (D-INFK) (Fall 16).