Department of Computer Science

Theory of Combinatorial Algorithms
Prof. Emo Welzl
up print 
People
Activity Report
Previous Reports
    2013
    2012
    2011
    2010
    2009
    2008
    2007
    2006
    2005
    2004
    2003
    2002
    2001
    2000
    1999
    1998
    1997
    1996
Research
Mittagsseminar
Teaching
Workshops
Social Activities

Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2006

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


Personnel



Guests


  • Takeaki Uno, National Institute of Informatics, Tokyo, Japan (until Aug 3)
    Maximization Problem of Intersection of Polytopes (Mittagsseminar, Jan 31, 2006)
    Constructing Canonical Form of Distance Hereditary Graphs (Mittagsseminar, Mar 21, 2006)
  • Berit Johannes (until Apr 30)
  • Andreas S. Schulz, Massachusetts Institute of Technology, Cambridge, MA (until Apr 30)
    Sometimes some NP-hard Problems can be solved in Polynomial Time (Mittagsseminar, Feb 2, 2006)
  • Masashi Kiyomi, National Institute of Informatics (NII), Japan (Feb 13 - Mar 1)
    Enumerating Chordal Graphs (Mittagsseminar, Feb 23, 2006)
  • Pavel Valtr, Department of Applied Mathematics, Charles University, Prague, Czech Republic (Apr 1 - May 31)
    Traversing the Cube (Mittagsseminar, May 16, 2006)
  • Jiří Matoušek, Department of Applied Mathematics, Charles University, Prague, Czech Republic (Apr 15 - Jul 8)
    Zone diagrams (Mittagsseminar, Apr 25, 2006)
    On the Johnson-Lindenstrauss Flattening Lemma (Mittagsseminar, May 4, 2006)
  • Gábor Fejes Tóth, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary (Apr 15 - Jun 14)
    A Short, Unconventional Introduction to Packing and Covering (Mittagsseminar, May 4, 2006)
  • Miloš Stojakovíc, Department of Mathematics and Computer Science, University of Novi Sad, Novi Sad, Serbia & Montenegro (May 4 - 20)
    The Game of Planarity (Mittagsseminar, May 9, 2006)
  • Dan Hefetz, The School of Computer Science, Tel Aviv Univiversity, Tel Aviv, Israel (May 6 - 13)
    Minor Games on the Complete Graph (Mittagsseminar, May 11, 2006)
  • Shakhar Smorodinsky, Courant Institute for Mathematical Sciences, New York University, USA (May 15 - 19)
  • Jakub Cerný, Department of Applied Mathematics, Charles University, Prague, Czech Republic (May 22 - Jun 16)
    Geometric and Topological Graphs with No Forbidden Subgraphs (Mittagsseminar, May 23, 2006)
  • Bettina Speckmann, Department of Mathematics and Computer Science, TU Eindhoven, Netherlands (Jun 16 - Jun 23)
    Kinetic Collision Detection for Convex Fat Objects (Mittagsseminar, Jun 20, 2006)
  • Eran Nevo, Department of Mathematics, Hebrew University, Jerusalem, Israel (Jun 16 - Jun 30)
    Combinatorial Embedding Obstructions for Simplicial Complexes (Mittagsseminar, Jun 22, 2006)
  • Tetsuo Asano, School of Information Science, JAIST (Japan Advanced Institute of Science and Technology), Ishikawa, Japan (Jun 25 - 29)
    Angular and Aspect-Ratio Voronoi Diagram with Applications (Mittagsseminar, Jun 27, 2006)
  • Joachim Giesen, Max-Planck-Institut für Informatik, Saarbrücken, Germany (Jun 25 - Jul 11, Nov 29 - Dec 10, Dec 18 - 19)
    Medial Axis Approximation and Unstable Flow Complex (Mittagsseminar, Nov 30, 2006)
  • Yoshio Okamoto, Discrete Optimization Laboratory, Department of Information and Computer Sciences, Toyohashi University of Technology, Japan (Jun 26 - Jul 8)
    Enumeration Algorithmics for Multi-Criteria Optimization (Mittagsseminar, Jun 28, 2006)
  • Shuji Kijima, Tokyo University, Japan (Jun 26 - Jul 1)
    Perfect Sampler for Closed Jackson Networks (Mittagsseminar, Jun 29, 2006)
  • Carsten Lange (Jun 29 - Jul 5)
    Realisations for the Associahedron and the Cyclohedron (Mittagsseminar, Jun 30, 2006)
  • Jozsef Solymosi, Department of Mathematics, University of British Columbia, Vancouver, Canada (Jul 2 - 10)
    Examples of when Number Theory and Incidence Geometry Intertwine (Mittagsseminar, Jul 5, 2006)
  • Ola Svensson, IDSIA, Lugano, Switzerland (Jul 3-7)
    Linear Complementarity for Infinite Games on Graphs (Optimisation Seminar, Jul 3, 2006)
  • Csaba Tóth, Massachusetts Institute of Technology, Cambridge, MA (Jul 3-7)
    Spanning Trees and Cuttings across Disks and Axis-Aligned Rectangles in Three-Space (Mittagsseminar, Jul 5, 2006)
  • Pavel Valtr, Department of Applied Mathematics, Charles University, Prague, Czech Republic (Aug 21-31)
    Paths with no Small Angles (Mittagsseminar, Aug 29, 2006)
  • Michael Krivelevich, Department of Mathematics, Tel Aviv University, Israel (Sep 16-22)
    Packing Hamilton Cycles in Random Graphs (Mittagsseminar, Sep 19, 2006)
  • Josep Diaz, Software Department, Technical University of Catalunya, Barcelona, Spain (Dec 18)

Grants


  • Stable Medial Axis under Motion

    (Funded by the Swiss National Science Foundation.) The medial axis is one of the fundamental geometric concepts in computational geometry, 3D shape modeling, and image processing. Introduced by Blum as a tool for image analysis, the medial axis has since then been used in many different contexts, e.g., shape recognition, motion planing and reverse engineering.
    Our interest in the medial axis is twofold. First, the medial axis is a very interesting mathematical object in itself that poses many computational and mathematical challenges. Second, the medial axis conceptually appears in many geometric modeling applications. In most of these applications a shape is given to us only in form of a finite sample, e.g., a laser range scan of a 3D solid, or a set of positions of the atoms of a molecule measured by x-ray crystallography. The use of the medial axis for such data has been mostly restricted to theoretical analysis. Few applications have been presented that explicitly compute the medial axis for geometric processing tasks on acquired sample sets. One of the main reasons for its limited practical use is the notorious instability of the medial axis transform.
    Our goal is to give a new definition of an approximate medial axis that is stable under a set of meaningful perturbations and at the same time respects the intrinsic scales of the data. This would allow scalable geometric processing operations based on the medial axis for non-uniformly sampled data, thus greatly enhancing the set of potential input data. Additionally, we want to derive algorithms for maintaining the medial axis for kinetic data sets, i.e., shapes that move or deform over time. Motion is fundamental in many disciplines that model the physical world, such as robotics, computer graphics, computational biology, or physics. A kinetic medial axis is of great interest in such fields, as it is directly linked to the concept of an interface between two or more different shapes. An interface can be defined as the subset of the medial axis of the dual shape that contains all points with nearest neighbors in more than one shape. Interfaces play an important role in machine learning as decision boundaries, in fluid dynamics simulations as boundary between different fluids, and in molecular dynamics simulations as inter-molecular or contact surfaces between different macromolecules.

    Contact: J. Giesen, M. Pauly (Institute of Computational Sciences)

  • Games and Geometric Unique Sink Orientations

    (Financed by the Swiss National Science Foundation.) In the first part of the project, we will be dealing with combinatorial structure in games and matrix classes. This is motivated by the recent research that links certain well-studied classes of games to exactly the abstract combinatorial models we were studying in the project Combinatorial Models for Geometric Optimization. This research concerns the classes of simple stochastic games, mean payoff games and parity games.
    The second part of the project deals with specific unique sink orientations (USO) arising from geometric applications. Within the former project Combinatorial Models for Geometric Optimization, we have shown that a USO is hidden behind any linear program (LP), and that this USO has a special property: it satisfies the Holt-Klee condition, a combinatorial condition concerned with directed paths in the USO. We call such a USO geometric.

    Contact: B. Gärtner, T. Szabó

  • An Approach to Efficient Practical Enumeration Algorithms for Geometric and Graphic Structures from the Theory of Enumeration Methods

    (Financed by the Swiss National Science Foundation.) The main topic of this research is developing new algorithms for enumerating combinatorial objects, such as graphs and polytopes. These objects have some difficulty from the aspects of computational complexity, for example no polynomial time algorithm for checking the isomorphism of two graphs is known. However, these enumeration problems have many applications in optimizations, clustering, data mining, and machine learning, thus we need developments of efficient algorithms, in the sense of both theory and practice.

    Contact: K. Fukuda, T. Uno

  • Revisiting the Flexibility of Proteins

    (Funded by INRIA.) Understanding the way proteins adopt their 3D structure, the folding problem, or the way macro-molecular complexes get formed, the docking problem, are two of the most challenging problems in structural biology. Since proteins in vivo vibrate at various frequencies addressing the aforementioned problems requires modeling protein flexibility. In this project we plan on developing new approaches towards modeling protein flexibility based on geometric and topological tools.

    Contact: F. Cazals (INRIA Sophia Antipolis, project leader), M. Nilges (Institut Pasteur), J. Giesen

  • Transversals and Colorings of Graphs

    (Financed by the Swiss National Science Foundation.) Proper coloring of graphs and the chromatic number (the smallest number of colors which allow a proper coloring) are among the most important concepts of graph theory. Numerous problems of pure mathematics and theoretical computer science require the study of proper colorings and even more real-life problems require the calculation or at least an estimation of the chromatic number. Nevertheless, there is the discouraging fact that the calculation of the chromatic number of a graph or the task of finding an optimal proper coloring are both famous intractable problems, even fast approximation is probably not possible. This is one of our motivations to study relaxations of proper coloring, because in some theoretical or practical situations a small deviation from proper is still acceptable, while the problem could become tractable. Another reason for the introduction of relaxed colorings is that in certain problems the use of the full strength of proper coloring is an ``overkill''. Often a weaker concept suffices and provides better overall results.
    In the project we study a relaxation of proper coloring, which allows the presence of some small level of conflicts in the color assignment.
    Our approach relies heavily on the theory of transversals. A set of vertices in a partitioned graph is called a transversal if it contains exactly one vertex from each class. Transversals with special properties surface in many different problems of combinatorics and theoretical computer science, when an appropriate auxiliary graph is constructed and a transversal of a certain kind is sought after. In particular independent transversals saw numerous applications in the study of list chromatic number, the satisfiability of boolean formulas, the linear arboricity of graphs and relaxed colorings of graphs. The quest for transversal results also inspired a great methodological advance in the field of combinatorics, as beautiful proofs applying combinatorial topology appeared.

    Contact: T. Szabó

  • Algorithms for Complex Shapes with Certified Numerics and Topology (ACS)

    (European Project.) Increasingly demanding applications of geometric computing, for example in CAD/CAM, computer aided surgery, realistic virtual environments, robotics, and molecular modeling in drug design and structural biology, require efficient and robust methods for computing with complex shapes. This project aims at advancing the state of the art in this field. Current technology can cope well with curves in the plane and smooth surfaces in three-dimensional space. We want to deal with a larger class of shapes, including piecewise smooth and singular surfaces.
    Topics that we address are shape approximation (including meshing and simplification), shape learning (including reconstruction and feature extraction), as well as robust modeling (including boolean operations). Our work on these topics will be closely intertwined with basic research on shape representations, certified geometric calculus and algorithms producing output with guaranteed topology.
    A distinctive feature is the design and implementation of novel algorithmic solutions with certified topology and numerics as an alternative for heuristics and ad hoc methods, and the development of an experimental geometry kernel for modeling and computing with complex shapes as a proof-of-concept justifying our approach. The results of this project should be directly useful to the application areas mentioned above. We intend to disseminate our work by publication in the appropriate applied research forums, by organizing multidisciplinary workshops aimed at exchange of knowledge and discussion of our work. Moreover, we aim at transferring our new technology by producing high quality software, demonstrating the feasibility of our techniques in practice. Cooperation with our industrial partner includes the assessment, trial, validation and packaging of the software developed in the project, thus guaranteeing a smooth transfer of new technology to application areas.
    At ETH, we focus on new geometric data structures and optimization-based primitives to deal with shapes, and we provide according software components, building on our experience with reconstruction and optimization software for various tasks.

    Contact: B. Gärtner, J. Giesen

  • Non-linear Manifold Learning

    (Financed by the Swiss National Science Foundation.) Manifold learning is the problem of computing a model of a k-dimensional manifold embedded non-linearly in d-dimensional Euclidean space only from a finite set of sample points. Typically k is very small compared to d. The importance of the problem can be stressed by its many applications, e.g. in speech recognition, weather forecasting and economic prediction.
    Special cases of the manifold learning problem in low dimensions received a lot of attention in recent years. Most prominent is the surface reconstruction problem where a two-dimensional manifold embedded in three-dimensional space has to be learned. Some of the proposed algorithms for surface reconstruction come with the guarantee that the computed model is a manifold homeomorphic and geometrically close to the unknown manifold provided some sampling condition is fulfilled. Almost all known provable algorithms for surface reconstruction use the Delaunay triangulation of the sample points as basic data structure. Unfortunately the time to compute the Delaunay triangulation is prohibitive in higher dimensions.
    In this project we plan to investigate provable methods for manifold learning in high dimensions. Starting point should be a sampling condition similar to the one used in the proofs for surface reconstruction. The most important task in extending theoretical guarantees known from surface reconstruction to higher dimensions is to replace the Delaunay triangulation with other proximity data structures.

    Contact: J. Giesen

  • Combinatorial Models for Geometric Optimization Problems

    (Financed by the Swiss National Science Foundation.) Linear programming, as well as several other geometric optimization problems do have polynomial-time algorithms in the bit model, i.e. when the input size is measured by the bit complexity of the actual numbers in the data. It is not known, however, whether there are strongly polynomial algorithms, whose performance is quantified in terms of arithmetic operations on input numbers, independently from their bit complexity. The goal of the project is to find, study, and algorithmically exploit combinatorial models for certain discrete geometric optimization problems. Our main motivation is to enhance our understanding of the combinatorics behind linear programming and related - mostly geometric - optimization problems, improve on the performance guarantees of existing algorithms, and possibly discover novel, more efficient approaches. Classical such models are matroids, oriented matroids and submodular functions.
    Within the last ten years, the concept of LP-type problems has become a recognized combinatorial model for linear programming and many other important geometric optimization problems. For many problems in the class, the currently best (or even optimal) combinatorial algorithm is an algorithm for general LP-type problems.
    In the last couple of years new exciting combinatorial models for geometric optimization problems have emerged, such as unique-sink orientations of cubes and strong LP-type problems. Just like LP-type problems ten years ago, these new combinatorial abstractions had immediate consequences; they provide the only available algorithms for certain linear complementarity problems with nontrivial running time guarantees.
    Within this new project, we plan to explore unique-sink orientations, strong LP-type problems, their relations to each other and to other known combinatorial models, as well as algorithms for problems fitting into the respective models.

    Contact: B. Gärtner, T. Szabó

  • Computational Geometry Aspects of Gamut Mapping

    (Financed by the Eidgenössische Materialprüfungs- und Forschungsanstalt, EMPA.) The set of colors that can be represented or reproduced by some device or process is called a gamut. In general different devices have different gamuts. Hence, when processing images from some input device to some output device one often faces the problem that the gamut changes, often the size of the gamut of the output device is the bottleneck in the transition and information gets lost. The challenge is to define and compute good (tailored) gamut mappings.
    The problem of defining and computing gamut mappings is amenable to methods from low dimensional computational geometry, because in color spaces like CIELAB a gamut is represented as a three-dimensional polytope.
    The purpose of this project is to develop fast and robust methods for computing gamuts and gamut mappings.

    Contact: J. Giesen, K. Simon, EMPA

  • Algorithms for Robust Conjoint Analysis

    (Financed by the Swiss National Science Foundation.) Estimating product preferences of individuals by means of questionnaires is daily practice in market research. Under the name of conjoint analysis a whole family of methods has been developed and used to estimate the preferences of individuals. Conjoint analysis started in 1964 with the seminal paper by Luce and Tukey and was introduced to the marketing literature by Green and Rao in 1971. Since then conjoint analysis has received much attention from practitioners in market research as well as from researchers in academia. Its importance can be stressed by its many applications, e.g. in new product planning, product improvement, pricing, advertising, distribution and market segmentation and simulation.
    In this project we study a variant of conjoint analysis which is called choice based conjoint analysis (CBC). In CBC product preferences of an individual are learned from a sequence of pairwise product comparisons. In each comparison the respondent only has to state which out of the two products she prefers. The comparisons are used to estimate parameters in a utility function that is defined over the product space. We focus on two questions. First, how many comparisons have to be performed by the respondent at least in order to get optimal knowledge on the parameters. Second, we want to find a strategy to present product pairs to the respondent such that one gets optimal knowledge on the parameters by presenting only the minimum number of product pairs necessary. That is, we want to determine the intrinsic complexity of CBC. The first problem asks for a lower bound on this complexity whereas the second problem asks for an upper bound.

    Contact: J. Giesen

  • Polytopes, Matroids and Polynomial Systems - Studies through the Fusion of Geometric, Combinatorial and Algebraic Algorithms

    (Financed by the Swiss National Science Foundation.) This project concerns research themes that interlink four domains in mathematics: combinatorics, algebra, geometry and optimization. We address fundamental questions and applications that rely crucially on this fusion.
    Our strong drive for this fusion of the established research domains comes from the observation that several fundamental problems spreading over these domains are closely interlinked: a solution to one of the problems often leads to a solution for another one in a different domain. More precisely, we propose to study the following four specific research themes (with its principal domain).

    1. Classifications of Oriented Matroids (Combinatorics)
    2. State Polytopes of Polynomial Ideals (Algebra)
    3. Minkowski Addition of Polytopes and Convex Hull (Geometric Computation)
    4. Solving Polynomial Systems and SDPs via Structure Information (Optimization)

    Each of the four themes has a long history of earlier investigations in its principal domain. With these themes studied extensively for many years, it is becoming increasing evident that these four themes are closely related and inseparable.
    In fact, there are underlying mathematical structures, convex polytopes, matroids and polynomials common to all these themes. Our belief is that it makes much more sense to investigate them together. Our research team consists of active researchers, each with at least two domains of competence and strong interests in making this nontrivial fusion.

    Contact: E. Feichtner, ETHZ, K. Fukuda, ETHZ and EPFL, P. Parrilo, ETHZ, R. Thomas, University of Washington


Publications


  • Books

    B. Gärtner, J. Matoušek, Understanding and Using Linear Programming, Universitext, Springer (2006).

  • Journals (with refereeing)

    U. Adamy, M. Hoffmann, J. Solymosi, M. Stojakovic, Coloring octrees, Theoretical Computer Science 363:1 (2006) 11-17.

    J. Bang-Jensen, B. Reed, M. Schacht, R. Samal, B. Toft, U. Wagner, On six problems posed by Jarik Nesetril, In: Topics in Discrete Mathematics (M. Klazar, J. Kratochvil, M. Loebl, J. Matoušek, R. Thomas, eds.), Algorithms and Combinatorics 26 (2006) 613-627.

    J. Barat, J. Matoušek, D. Wood, Bounded-degree graphs have arbitrarily large geometric thickness, The Electronic Journal of Combinatorics 13:1 (2006).

    K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, Sh. Smorodinsky, U. Wagner, E. Welzl, Online conflict-free coloring for intervals, SIAM Journal of Computing 36 (2006) 956-973.

    V.G. Deineko, M. Hoffmann, Y. Okamoto, G.J. Woeginger, The traveling salesman problem with few inner points, Operations Research Letters 34:1 (2006) 106-110.

    R. Haas and M. Hoffmann, Chordless paths through three vertices, Theoretical Computer Science 351:3 (2006) 360-371.

    P. Haxell, T. Szabó, Odd independent transversals are odd, Combinatorics, Probability and Computing 15:1-2 (2006) 193-211.

    J. Matoušek, The number of unique-sink orientations of the hypercube, Combinatorica 26 (2006) 91-99.

    J. Matoušek, M. Sharir, S. Smorodinsky, U. Wagner, k-sets in four dimensions, Discrete Computational Geometry 35:2 (2006) 177-191.

    J. Matoušek, T. Szabó, RANDOMEDGE can be exponential in abstract cubes, Advances in Mathematics 204 (2006) 262-277.

    M. Sharir, E. Welzl, On the number of crossing-free matchings, cycles, and partitions, SIAM Journal of Computing 36 (2006) 1342-1359.

    T. Szabó, G. Tardos, Extremal problems for transversals in graphs with bounded degree, Combinatorica 26:3 (2006) 333-351.

  • Conference Proceedings (with selection process)

    T. Asano, J. Matoušek, T. Tokuyama, The distance trisector curve, Proc. 38th ACM Symposium on Theory of Computing (STOC) (2006) 336-343.

    R. Berke, T. Szabó, Deciding relaxed two-colorability - a hardness jump, Proc. 14th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 4168 (2006) 124-135.

    B. Gärtner, J. Matoušek, L. Rüst, P. Škovroň, Violator spaces: structure and algorithms, Proc. 14th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 4168 (2006) 387-398.

    B. Gärtner, I. Schurr, Linear Programming and unique sink orientations, Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006) 749-757.

    J. Giesen, E. Ramos, B. Sadri, Medial axis approximation and unstable manifolds, Proc. 22nd Annual ACM Symposium on Computational Geometry (SoCG) (2006) 327-336.

    J. Giesen, E. Schuberth, K. Simon, D. Zeiter, P. Zolliker, A framework for image-dependent gamut mapping, Proc. IS&T/SPIE Symposium on Electronic Imaging (2006) 605805-1-11.

    J. Giesen, E. Schuberth, M. Stojakovic, Approximate sorting, Proc. 7th Latin American Theoretical Informatics Symposium (LATIN), Lecture Notes in Computer Science 3887 (2006) 524-531.

    M. Kiyomi, S. Kijima, T. Uno, Listing chordal graphs and interval graphs, Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (2006) 68-77.

    N. Mitra, L. Guibas, J. Giesen, M. Pauly; Probabilistic fingerprints for shapes, Proc. 4th Symposium on Geometry Processing (SGP) (2006) 121-130.

    M. Sharir, E. Welzl, On the number of crossing-free matchings, (cycles, and partitions), Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006) 860-869.

    M. Sharir, E. Welzl, Random triangulations of planar point sets, Proc. 22nd Annual ACM Symposium on Computational Geometry (SOCG) (2006) 273-281.

    U. Wagner, On a generalization of the Upper Bound Theorem, Proc. 47th Annual Symposium on the Foundations of Computer Science (FOCS) (2006) 635-645.

  • Other (including submitted work)

    K. Fukuda, T. Uno, Algorithms for maximizing the volume of intersection of polytopes, Proc. 22nd European Workshop on Computational Geometry (EuroCG) (2006).

    J. Giesen, E. Schuberth, K. Simon, P. Zolliker, A kernel approach to gamut boundary computation, Proceedings of the 14th European Signal Processing Conference (EUSIPCO) (2006) (invited paper).

    M. Hoffmann, Cs. D. Tóth, Spanning trees across axis-parallel segments, Proc. 18th Canadian Conference on Computational Geometry (CCCG), Kingston (ON), Canada (2006) 101-104.

    E. Welzl, Kleinster umschliessender Kreis - Ein Demokratiebeitrag aus der Schweiz?, Algorithmus der Woche 42 (2006).

    E. Welzl, Random triangulations of planar point sets, in: Algorithmic Graph Theory, Oberwolfach Reports 7 (2006) 432-435.


Lectures


R. BERKE
"Deciding Relaxed Two-Colorability", Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 11, 2006).
"Relaxed Two-Coloring of Cubic Graphs", Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17, 2006).
"Deciding Relaxed Two-Colorability - A Hardness Jump", 14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 13, 2006).

B. GÄRTNER
"Linear Programming and Unique Sink Orientations", 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, Florida, USA (Jan 23, 2006).
Short course: "Linear Programming Methods", Part of the Predoc-Course Optimization Methods in Discrete Geometry, Technical University Berlin, Germany (We/Th Apr 5-20, 2006).
"Simple Stochastic Games, Linear Complementarity Problems, and Unique Sink Orientations", London School of Economics, London, Great Britain (May 26, 2006).
"Clarkson's Randomized Linear Programming Algorithms Revisited", Mini-Symposium on Random Discrete Structures and Algorithms, Jahrestagung der Deutschen Mathematiker-Vereinigung, Universität Bonn, Germany (Sep 21, 2006).

M. HOFFMANN
"Connecting Line Segments", Symposium Diskrete Mathematik 2006, Technical University Berlin, Berlin, Germany (Apr 4, 2006).

L. RÜST
"Violator Spaces: Structure and Algorithms", 14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 12, 2006).

D. SCHEDER
"Approximation Algorithms for Multi-Criteria Traveling Salesman Problems", Fourth Workshop on Approximation and Online Algorithms, ETH Zurich, Switzerland (Sep 14, 2006).

E. SCHUBERTH
"A Framework for Image-dependent Gamut Mapping", IS&T/SPIE 18th Annual Symposium on Electronic Imaging, San Jose, USA (Jan 17, 2006).
"Approximate Sorting", Latin American Theoretical Informatics Symposium (LATIN), Valdivia, Chile (Mar 21, 2006).
"Preference Analysis", DIMACS Workshop on Polyhedral Combinatorics of Random Utility, DIMACS center, Rutgers University, New Jersey (May 24, 2006).
"Einführung in Java (Teil 2)", Schnupperstudium am Departement Informatik ETH Zurich, Switzerland (Aug 30 and Sep 1, 2006).
"A Kernel Approach to Gamut Boundary Determination", 14th European Signal Processing Conference (EUSIPCO), Florence, Italy (Sep 6, 2006).
"Psychovisuelle Tests für Parametrisierte Algorithmen", Meeting of Departement 292, EMPA Zurich, Switzerland (Nov 10, 2006).
"Frauenförderung am Departement Informatik der ETH Zürich - Erfahrungen und Motivation", Swiss ICT- KNIT, ETH Zurich, Switzerland (Nov 30, 2006).

T. SZABÓ
"Characters and the Projective Norm-Graphs", Doc-Course, Harmonic Analysis in Computer Science and Combinatorics, Charles University, Prague, Czech Republic (Feb 16, 2006).
"Relaxed Two-Coloring of Cubic Graphs", Theoretical Computer Science and Discrete Math Seminar, Institute for Advanced Study, Princeton, USA (Mar 20, 2006).
"Lower Bounds for Algorithms in Abstract Cubes", Discrete Math and Theory of Computing Seminar, Rutgers University, New Brunswick, USA (Mar 23, 2006).
"Making or Avoiding Planar Graphs", Geometry Seminar, Courant Institute, New York University, New York City, USA (Mar 28, 2006).
"Making, Breaking, Avoiding, Enforcing", Discrete Mathematics Seminar, Princeton University, Princeton, USA (Mar 29, 2006).
"Making vs Avoiding in Positional Games", Symposium Diskrete Mathematik 2006, Technical University Berlin, Berlin, Germany (Apr 3, 2006).
Short course: "Positional Games", Trimester Programme Phenomena in high dimension, Institute Henri Poincare, Paris, France (Apr 24-26, 2006).
"Making vs Avoiding in Positional Games" Workshop: Complexity of Games, Polyhedra and Lattice Points, FIM (Institute for Mathematical Research), ETH Zurich, Switzerland (May 18, 2006).
"Turán's Theorem in the Hypercube", Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 10, 2006).
"Turán's Theorem in the Hypercube", Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17, 2006).
"Relaxed Coloring of Cubic Graphs -- Extremal Graph Theory meeting Complexity Theory", Workshop on Combinatorics, Probability, and Computing, Mathematisches Forschungsinstitut Oberwolfach, Germany (Oct 29, 2006).
"Making vs. Avoiding in Positional Games", MHC Autumn School in Discrete Algorithms, Seto, Japan (Nov 15, 2006).

E. WELZL
"On the Number of Crossing-Free Matchings, (Cycles, and Partitions)", 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, Florida, USA (Jan 24, 2006).
"On the Number of Crossing-Free Configurations on Planar Point Sets", Colloquium Combinatorics, Geometry, and Computation, Technical University Berlin, Germany (Jan 30, 2006).
"Random Triangulations of Planar Point Sets", Workshop on Algorithmic Graph Theory, Mathematisches Forschungsinstitut Oberwolfach, Germany (Feb 14, 2006).
"On the Number of Triangulations and other Crossing-Free Configurations on Planar Point Sets", Discrete and Computational Geometry -- Twenty Years Later, AMS-SIAM Summer Research Conference, Snowbird, Utah, USA (Jun 22, 2006; invited talk).
"Random Triangulations of Planar Points Sets", V Jornadas de Matemática Discreta y Algorítmica (V JDMA), Campus de Soria, Universidad de Valladolid, Spain (Jul 13, 2006; invited talk).
"The Number of Crossing-Free Configurations on Planar Point Sets", 14th International Symposium on Graph Drawing, Karlsruhe, Germany (Sep 18, 2006; invited talk).
"On the Number of (and Random) Triangulations on Planar Point Sets", Workshop on Combinatorics, Probability, and Computing, Mathematisches Forschungsinstitut Oberwolfach, Germany (Nov 2, 2006).
"Lattice Triangulations", Colloquium Methods for Discrete Structures, Berlin Free University, Germany (Nov 13, 2006).
"Combinatorics of Boolean CNF Formulas", Ramakrishna Mission Vivekananda University, Belur Math, Howrah, West Bengal, India (Dec 12, 2006).
"The Number of Crossing Free Configurations on Finite Point Sets in the Plane", 26th Conference on Foundations of Software Technology and Theoretical Computer Science, Indian Statistical Institute, Kolkata, West Bengal, India (Dec 13, 2006; invited talk).


Courses and Seminars


Winter 05/06

Summer 06


Organization of Workshops etc.



Dissertations


  • Shankar Ram Lakshminarayanan, Approximation Results for the Traveling Salesman and Related Problems
    Advisors: Markus Bläser, Universität des Saarlandes, Saarbrücken, Germany (referee) / Co-referees: Lars Engebretsen, Google Switzerland GmbH; Emo Welzl / Defense: Aug 21, 2006
  • Dieter Mitsche, Spectral Methods for Reconstruction Problems
    Advisors: Joachim Giesen, Emo Welzl (referee) / Co-referees: Josep Diaz, Universitat Politecnica de Catalunya, Barcelona; Joachim Giesen, MPI für Informatik, Saarbrücken / Defense: Dec 18, 2006

Diploma/Master Theses


  • Jutta Bonan, Gamut Mapping Using Support Vector Machines
    Advisors: J. Giesen, E. Schuberth / 2.3.2006
  • Yves Brise, Structure and Generation of Splitting Rules for SAT
    Advisors: Ph. Zumstein, E. Welzl / 2.10.2006
  • Michael Bumann, Visualizing Concepts in Satisfiability
    Advisors: A. Razen, Ph. Zumstein, E. Welzl / 31.8.2006
  • Michael Eigensatz, Detecting Shape Features in Sampled Surfaces Using the Slab SVM
    Advisors: J. Giesen, M. Pauly, J. Buhmann / 16.3.2006
  • Martin Jaggi, Linear and Quadratic Programming by Unique Sink Orientations
    Advisor: B. Gärtner / 9.9.2006
  • Claudia Käppeli, Partial Satisfaction under Local Constraints
    Advisors: D. Scheder, E. Welzl / 11.10.2006
  • Balint Miklos, The Medial Axis and Growing Balls
    Advisors: J. Giesen, M. Pauly / 5.9.2006
  • Samuel Zürcher, Anistropic Smallest Enclosing Balls
    Advisor: B. Gärtner / 28.2.2006

Semester Theses / Internship Projects


  • Bhaskara Aditya, k-Wise Intersection Theorems
    Advisor: T. Szabo / 5.7.2006
  • Anshul Gandhi, Perfectly Centered Neighborly Polytopes
    Advisor: U. Wagner / 5.7.2006
  • Dominic Meier, k-Satisfiable CNF Formulas with and without Repetitions
    Advisor: E. Welzl / 7.7.2006
  • Robin Moser, On the Search for Solutions to Bounded Occurrence Instances of SAT
    Advisor: E. Welzl / 15.7.2006
  • Amit Smotra, Improving CGAL's Quadratic Programming Solver
    Advisor: B. Gärtner / 5.7.2006
  • Daniel Zeiter, Image Dependent Gamut Mapping
    Advisors: J. Giesen, E. Schuberth / 3.3.2006
  • Samuel Zuercher, Small Excluded Submatrices
    Advisor: R. Berke / 3.3.2006
  • Oliver Zweifel, Psycho-Physical Test for Image Dependent Gamut Mapping
    Advisors: J. Giesen, E. Schuberth / 22.3.2006

Miscellaneous


R. BERKE
Teach. Assistance Graph Theory (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Teach. Assistance Coordinator.
Attended the conferences/courses/workshops:
Symposium Diskrete Mathematik, Berlin, Germany (Apr 3-4, 2006).
Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 10-15, 2006).
Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17-21, 2006).
Summer School - Extremal Graph Theory and Random Graphs, Chorin, Germany (Jul 31 - Aug 4, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).

Y. BRISE
Attended the conferences/courses/workshops:
Algorithms for the SAT problem, Humboldt-Universität Berlin, Germany (Oct 27-29, 2006).

K. FISCHER
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS05/06).

K. FUKUDA
Courses taught:
"Predoc-Course: Polyhedral Computation", Optimization Methods in Discrete Geometry, Berlin, Germany (May 17 - Jun 2, 2006).
"Discrete and Algorithmic Geometry" (with A. Prodon), Graduate Course, EPF Lausanne, Switzerland (WS05/06).

Editor of European Journal of Combinatorics, Applied Mathematics Research eXpress.

Member of

B. GÄRTNER
Coordinator ACS.
Member of the CGAL Editorial Board.
Editor of a special issue of Computational Geometry: Theory and Applications on CGAL.
PhD examiner for Rahul Savani, London School of Economics, London, GB (Jun 26, 2006).

J. GIESEN
Program committee member of

  • Symposium on Point-Based Graphics, Boston, USA (2006)

M. HOFFMANN
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS05/06).
Informatik Koordinator.
Member of the CGAL Editorial Board.

S. LAKSHMINARAYANAN
Teach. Assistance External Memory Algorithms and Data Structures (WS05/06).

D. MITSCHE
Teach. Assistance Logik (WS05/06).
Coordinator Mittagsseminar (until Mar 31).

A. RAZEN
Teach. Assistance Erfüllbarkeit logischer Formeln (WS05/06).
Teach. Assistance Extremal Combinatorics (SS06).
Coordinator Mittagsseminar (since Apr 1).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation, Prague, Czech Republic (Feb 2 - Mar 3, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).

L. RÜST
Teach. Assistance Digitales Publizieren I: Farbwiedergabe (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Webmaster www-gremo.
Attended the conferences/courses/workshops:
Summer School on Game Theory, University of Aarhus, Denmark (Jun 26-30, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).

D. SCHEDER
Teach. Assistance Logik (WS05/06).
Teach. Assistance Seminar SAT (SS06).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation, Prague, Czech Republic (Feb 2 - Mar 3, 2006).

E. SCHUBERTH
Teach. Assistance Algorithmische Geometrie (WS05/06).
Teach. Assistance Approximate Methods in Geometry (SS06).
Head of Frauenförderung.
Presentation of booth on Gamut Mapping and Psychovisual Tests at 25 Years of Computer Science at ETH exhibition "Die Welt zwischen 0 und 1" (Oct 20-29, 2006).
Attended the conferences/courses/workshops:
IS&T/SPIE 18th Annual Symposium on Electronic Imaging, San Jose, USA (Jan 15-19, 2006).
Latin American Theoretical Informatics Symposium (LATIN), Valdivia, Chile (Mar 20-24, 2006).
DIMACS Workshop on Polyhedral Combinatorics of Random Utility, DIMACS center, Rutgers University, New Jersey (May 24-26, 2006).
14th European Signal Processing Conference (EUSIPCO), Florence, Italy (Sep 4-8, 2006).

P. TRAXLER
Teach. Assistance Approximation: Theorie & Algorithmen (SS06).

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.
Vice-Chair, Department of Computer Science, ETH Zurich (until Sep 30).

Program committee member of

Editorial Board member of

Member (chair, contact person) of selection committees for

Member of the EATCS Council (European Association for Theoretical Computer Science).

Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Algorithmik grosser und komplexer Netzwerke" der Deutschen Forschungsgemeinschaft (DFG).
Mitglied der Studienkommission der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.

Coreferee for habilitation of

  • Alexander Wolff, Geometrische Netzwerke und ihre Visualisierung (Karlsruhe University, Germany)

P. ZUMSTEIN
Teach. Assistance Theory of Computing (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation, Prague, Czech Republic (Feb 2 - Mar 3, 2006).
Summer School - Extremal Graph Theory and Random Graphs, Chorin, Germany (Jul 31 - Aug 4, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).
Algorithms for the SAT problem, Humboldt-Universität Berlin, Germany (Oct 27-29, 2006).


10-Oct-2012 / stich@inf.ethz.ch