Department of Computer Science

Theory of Combinatorial Algorithms
Prof. Emo Welzl
up print 
Activity Report
Previous Reports
Social Activities

Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2015

Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl

Institut für Theoretische Informatik
Departement Informatik
ETH Zürichphone +41-44-632 73 92
CH-8092 Zürichfax+41-44-632 10 63



  • Otfried Cheong, KAIST, South Korea (Jan 1-9)
    Approximating Convex Shapes to Minimize the Symmetric Difference (Mittagsseminar, Jan 6, 2015), Host: E. Welzl.
  • Uli Wagner, Institute of Science and Technology Austria, Klosterneuburg, Austria (Jan 13 -18), Host: E. Welzl.
  • Kenneth L. Clarkson, IBM Almaden Research Center, USA (Jan 19-23)
    A Unified Approach to Robust Regression (Mittagsseminar, Jan 20, 2015), Host: E. Welzl.
  • Yasuko Matsui, Tokai University, Japan (Feb 23-25), Host: K. Fukuda.
  • Hidefumi Hiraishi, University of Tokyo, Japan (Feb 27 - Mar 20), Host: K. Fukuda.
  • Yasuyuki Tsukamoto, Kyoto University, Japan (Mar 2-6)
    Objects with projection images just like a cube (Mittagsseminar, Mar 3, 2015), Host: K. Fukuda.
  • Sonoko Moriyama, Tohoku University, Sendai, Japan (Mar 4-13), Host: B. Gärtner.
  • Hanna Sumita, University of Tokyo, Japan (Mar 16-20)
    The Linear Complementarity Problem: Sparsity and Integrality (Mittagsseminar, Mar 19, 2015), Host: B. Gärtner.


  • Crossing-Free Configurations in the Plane - Counting, Enumeration, and Sampling

    (Financed by the Swiss National Science Foundation - EuroGIGA/ComPoSe). The goal of this project is the understanding of crossing-free geometric graphs-these are graphs with an embedding on a given planar point set where the edges are drawn as straight line segments without crossings. Often we are restricted to certain types of graphs, most prominently triangulations, but also spanning cycles, spanning trees or (perfect) matchings (and crossing-free partitions), among others. A primary goal is to enumerate, count, or sample graphs of a certain type for a given point set-so these are algorithmic questions-, or to give estimates for the maximum and minimum number of such graphs on any set of n points-these are problems in extremal combinatorial geometry.

    Contact: E. Welzl, M. Wettstein

  • Programmieren von klein auf in der ETH Zürich

    (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.

  • Redundancy in Linear and Neuromuscular Systems

    (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.


  • Books

  • Journals (with refereeing)

    I. Bárány, J. Matoušek, A. Por, Curves in Rd intersecting every hyperplane at most d+1 times, J. European Math. Soc. (2014), to appear.

    J. Cardinal, V. Kusters, The Complexity of Simultaneous Geometric Graph Embedding, Journal of Graph Algorithms and Applications (JGAA), 19:1 (2015), 259–272.

    D. Clemens, H. Gebauer, A. Liebenau, The random graph intuition for the tournament game, Combinatorics, Probability and Computing (2015), to appear.

    B. Gärtner, Sampling with Removal in LP-type Problems, Journal of Computational Geometry (JoCG), 6:2 (2015), 93-112.

    X. Goaoc, J. Matoušek, P. Paták, Z. Safernová, M. Tancer, Simplifying inclusion-exclusion formulas, Combinatorics, Probability and Computing (2014), to appear.

    J. Matoušek, Computing higher homotopy groups is W[1]-hard, Fundamenta Informaticae (2014), to appear.

    J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Untangling two systems of noncrossing curves, Israel J. Math. (2014), to appear.

    A. Thomas, J. van Leeuwen, Pure Nash Equilibria in Graphical Games and Treewidth, Algorithmica, 71:3 (2014), 581-604.

    H. Tyagi, S. Stich, B. Gärtner, On two continuum armed bandit problems in high dimensions, Theory of Computing Systems (2014), to appear.

  • Conference Proceedings (with selection process)

    J. Cardinal, M. Hoffmann, V. Kusters, Cs. D. Tóth, M. Wettstein, Arc diagrams, flip distances, and Hamiltonian triangulations, 32nd Symposium on Theoretical Aspects of Computer Science (STACS) (2015), 197-210.

    K. Fukuda, B. Gärtner, M. Szedlák, Combinatorial Redundancy Removal, 31st International Symposium on Computational Geometry (SoCG) (2015), to appear.

    B. Gärtner, A. Thomas, The Complexity of Recognizing Unique Sink Orientations, 32nd Symposium on Theoretical Aspects of Computer Science (STACS) (2015), 341-353.

    A. Pilz, E. Welzl, Order on Order Types, 31st International Symposium on Computational Geometry (SoCG) (2015), to appear.

  • Other (including submitted work)

    O. Aichholzer, V. Kusters, W. Mulzer, A. Pilz, M. Wettstein, An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings, (2015), submitted.

    L. Barba, M. Hoffmann, V. Kusters, Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs, Abstracts of the 31st European Workshop on Computational Geometry (EuroCG), Ljubljana, Slovenia (2015), 53-56.

    J. Cardinal, M. Hoffmann, V. Kusters, On Universal Point Sets for Planar Graphs, (2014), submitted.

    J. Cibulka, J. Matoušek, P. Paták, Three-monotone interpolation, (2014), submitted.

    B. Gärtner, C. Müller, S. Stich, Variable Metric Random Pursuit, (2012), submitted.

    V. Kusters, B. Speckmann, Characterizing Graphs With A Sliceable Rectangular Dual, (2013), submitted.

    J. Matoušek, Z. Safernová, Multilevel polynomial partitions and simplified range searching, (2014), submitted.


"Arc Diagrams, Flip distances, and Hamiltonian triangulations", Algebra, Number Theory, and Discrete Mathematics Seminar, CSUN, Los Angeles, USA (Mar 18, 2015).

"Arc diagrams, flip distances, and Hamiltonian triangulations", 32nd Symposium on Theoretical Aspects of Computer Science (STACS), TU Munich, Germany (Mar 5, 2015).
"Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs", European Workshop on Computational Geometry (EuroCG), University of Ljubljana, Slovenia (Mar 16, 2015).

Courses and Seminars

Spring 15

See also the Course Catalogue

Fall 14

See also the Course Catalogue

Organization of Workshops etc.


Master Theses

  • Jérome Dohrau, Edge Flips in Combinatorial Triangulations,
    Advisors: Michael Hoffmann, Vincent Kusters / to be completed
  • Luca Eggemann, Survey on Random SAT,
    Advisors: Timon Hertli, Emo Welzl / 24.2.2015
  • Nathanael Gutmann, Intersection Restricted Families of Sets,
    Advisors: Torsten Mütze, Emo Welzl / 9.3.2015
  • Jakob Olbrich, Screening Rules for Machine Learning Applications,
    Advisors: B. Gärtner, M. Jaggi / to be completed
  • Patrick Schnider, Partitions into Plane Spanning Trees,
    Advisors: Manuel Wettstein, Emo Welzl / to be completed

Bachelor and Semester Theses / Internship Projects

  • Stephan Ammann, Draw an outerplanar graph and a matching at the same time,
    Advisors: Michael Hoffmann, Vincent Kusters / to be completed
  • Michael Bühler, A new Algorithm for Linear programming,
    Advisors: B. Gärtner / to be completed
  • Christian Schneebeli, Polyhedral Boundary Detection with Random Walk,
    Advisors: Komei Fukuda, May Szedlák / to be completed
  • Pascal Su, Hamilton cycles in Kneser graphs,
    Advisors: Torsten Mütze, Emo Welzl / 23.3.2015
  • Julia Wysling, Screening Rules for Support Vector Machines,
    Advisors: B. Gärtner, M. Jaggi / to be completed


Editorial Board Member of European J. Combinatorics, Computational Geometry: Theory and Applications, Applied Mathematics Research eXpress.

Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Mobilitätsberater des Departements Informatik

Teach. Assistance Coordinator (until Feb 27, 2015).

Informatik Koordinator.
Member of the CGAL Editorial Board.

Coordinator Mittagsseminar.
Teach. Assistance Modelling and Simulation (D-INFK) (Spring 15).

Elected member of the

Editorial Board member of

Contact Assistant Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 15).

Webmaster www-gremo.
Teach. Assistance Modelling and Simulation (D-INFK) (Spring 15).

Member of the board (deputy head) of the Department of Computer Science, ETH Zurich.

Editorial/Advisory Board member of

Member (chair, contact person) of selection committees for

  • Assistant Professor of Plant Cell and Developmental Biology/Plant-Microbial Interactions, Department of Biology, ETH Zurich, (chair).
  • Assistant Professors (Tenure Track) of Computer Science (Software Engineering and Programming Languages, Information Systems, Theory), Department of Computer Science (D-INFK), ETH Zurich.
  • Professor of Agricultural Economies and Policy, and Professor/Assistant Professor (tenure track) of Agricultural and Resource Economics, Department of Management, Technology and Economics (D-MTEC) and Department of Environmental Systems Science (D-USYS), ETH Zurich (chair)
  • Professor of Applied Mathematics, Department of Mathematics, ETH Zurich, (chair).
  • Professor of Mathematics, Department of Mathematics, ETH Zurich.
  • Professor / Assistant Professor (Tenure Track) of Networked Systems, Department of Information Technology and Electrical Engineering, ETH Zurich.

Member of the

Delegierter für Professorenwahlen an der ETH Zürich.
Elected as a corresponding member to the Austrian Academy of Sciences (OeAW).

Teach. Assistance Coordinator (since Feb 28, 2015).


08-Jan-2015 /