Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl
Quick~Links: 
Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Semester Theses, Miscellaneous

Personnel

Professors
Fukuda, Komei (1/3 appointment)
Welzl, Emo

Research Associates and Ph.D. Students
Berke, Robert
Brise, Yves (since Oct 16)
Christ, Tobias (since Oct 1)
Fischer, Kaspar, Dr. (until Mar 31)
Gärtner, Bernd, Dr.
Giesen, Joachim, Dr. (until Mar 31)
Hoffmann, Michael, Dr.
Lakshminarayanan, Shankar Ram (until Sep 30)
Mitsche, Dieter
Razen, Andreas
Rüst, Leo
Scheder, Dominik
Schuberth, Eva
Sulovský, Marek (since Oct 1)
Szabó, Tibor, Dr.
Traxler, Patrick (since Apr 1)
Wagner, Uli, Dr. (since Apr 1)
Zumstein, Philipp

Administration
HeftiWidmer, Franziska
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 NPhard 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 JohnsonLindenstrauss 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 AspectRatio Voronoi Diagram with Applications
(Mittagsseminar, Jun 27, 2006)

Joachim Giesen,
MaxPlanckInstitut 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 MultiCriteria 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 37)
Linear Complementarity for Infinite Games on Graphs
(Optimisation Seminar, Jul 3, 2006)

Csaba Tóth,
Massachusetts Institute of Technology, Cambridge, MA (Jul 37)
Spanning Trees and Cuttings across Disks and AxisAligned Rectangles in ThreeSpace
(Mittagsseminar, Jul 5, 2006)

Pavel Valtr,
Department of Applied Mathematics, Charles University, Prague, Czech Republic (Aug 2131)
Paths with no Small Angles (Mittagsseminar, Aug 29, 2006)

Michael Krivelevich,
Department of Mathematics, Tel Aviv University, Israel (Sep 1622)
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 xray 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
nonuniformly 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
intermolecular 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
wellstudied 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 HoltKlee 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
macromolecular 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 reallife 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 threedimensional
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 proofofconcept
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 optimizationbased
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

Nonlinear Manifold Learning
(Financed by the Swiss National Science Foundation.)
Manifold learning is the problem of computing a model of a kdimensional manifold
embedded nonlinearly in ddimensional 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 twodimensional manifold embedded in threedimensional 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 polynomialtime 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 LPtype 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 LPtype problems.
In the last couple of years new exciting
combinatorial models for geometric optimization problems
have emerged, such as uniquesink orientations of cubes and
strong LPtype problems. Just like LPtype 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 uniquesink orientations,
strong LPtype 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 threedimensional 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).
 Classifications of Oriented Matroids (Combinatorics)
 State Polytopes of Polynomial Ideals (Algebra)
 Minkowski Addition of Polytopes and Convex Hull (Geometric Computation)
 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) 1117.
J. BangJensen, 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) 613627.
J. Barat, J. Matoušek, D. Wood,
Boundeddegree 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 conflictfree coloring for intervals,
SIAM Journal of Computing
36 (2006) 956973.
V.G. Deineko, M. Hoffmann, Y. Okamoto, G.J. Woeginger,
The traveling salesman problem with few inner points,
Operations Research Letters
34:1 (2006) 106110.
R. Haas and M. Hoffmann,
Chordless paths through three vertices,
Theoretical Computer Science
351:3 (2006) 360371.
P. Haxell, T. Szabó,
Odd independent transversals are odd,
Combinatorics, Probability and Computing
15:12 (2006) 193211.
J. Matoušek,
The number of uniquesink orientations of the hypercube,
Combinatorica
26 (2006) 9199.
J. Matoušek, M. Sharir, S. Smorodinsky, U. Wagner,
ksets in four dimensions,
Discrete Computational Geometry
35:2 (2006) 177191.
J. Matoušek, T. Szabó,
RANDOMEDGE can be exponential in abstract cubes,
Advances in Mathematics
204 (2006) 262277.
M. Sharir, E. Welzl,
On the number of crossingfree matchings, cycles, and partitions,
SIAM Journal of Computing
36 (2006) 13421359.
T. Szabó, G. Tardos,
Extremal problems for transversals in graphs with bounded degree,
Combinatorica
26:3 (2006) 333351.

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) 336343.
R. Berke, T. Szabó,
Deciding relaxed twocolorability  a hardness jump,
Proc. 14th Annual European Symposium on Algorithms (ESA),
Lecture Notes in Computer Science 4168
(2006) 124135.
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) 387398.
B. Gärtner, I. Schurr,
Linear Programming and unique sink orientations,
Proc. 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
(2006) 749757.
J. Giesen, E. Ramos, B. Sadri,
Medial axis approximation and unstable manifolds,
Proc. 22nd Annual ACM Symposium on Computational Geometry (SoCG)
(2006) 327336.
J. Giesen, E. Schuberth, K. Simon, D. Zeiter, P. Zolliker,
A framework for imagedependent gamut mapping,
Proc. IS&T/SPIE Symposium on Electronic Imaging
(2006) 605805111.
J. Giesen, E. Schuberth, M. Stojakovic,
Approximate sorting,
Proc. 7th Latin American Theoretical Informatics Symposium (LATIN),
Lecture Notes in Computer Science 3887
(2006) 524531.
M. Kiyomi, S. Kijima, T. Uno,
Listing chordal graphs and interval graphs,
Proc. 32nd International Workshop on GraphTheoretic Concepts in Computer Science (WG)
(2006) 6877.
N. Mitra, L. Guibas, J. Giesen, M. Pauly;
Probabilistic fingerprints for shapes,
Proc. 4th Symposium on Geometry Processing (SGP)
(2006) 121130.
M. Sharir, E. Welzl,
On the number of crossingfree matchings, (cycles, and partitions),
Proc. 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
(2006) 860869.
M. Sharir, E. Welzl,
Random triangulations of planar point sets,
Proc. 22nd Annual ACM Symposium on Computational Geometry (SOCG)
(2006) 273281.
U. Wagner,
On a generalization of the Upper Bound Theorem,
Proc. 47th Annual Symposium on the Foundations of Computer Science (FOCS)
(2006) 635645.

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 axisparallel segments,
Proc. 18th Canadian Conference on Computational Geometry (CCCG),
Kingston (ON), Canada
(2006) 101104.
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) 432435.
Lectures
R. BERKE
"Deciding Relaxed TwoColorability", Sixth CzechSlovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 11, 2006).
"Relaxed TwoColoring of Cubic Graphs", Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17, 2006).
"Deciding Relaxed TwoColorability  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 ACMSIAM Symposium on Discrete Algorithms,
Miami, Florida, USA
(Jan 23, 2006).
Short course: "Linear Programming Methods",
Part of the PredocCourse Optimization Methods in Discrete Geometry,
Technical University Berlin, Germany
(We/Th Apr 520, 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",
MiniSymposium on Random Discrete Structures and Algorithms,
Jahrestagung der Deutschen MathematikerVereinigung,
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 MultiCriteria Traveling Salesman Problems", Fourth Workshop on Approximation and Online Algorithms, ETH Zurich, Switzerland (Sep 14, 2006).
E. SCHUBERTH
"A Framework for Imagedependent 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 NormGraphs",
DocCourse, Harmonic Analysis in Computer Science and Combinatorics, Charles University,
Prague, Czech Republic
(Feb 16, 2006).
"Relaxed TwoColoring 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 2426, 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 CzechSlovak 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 CrossingFree Matchings, (Cycles, and Partitions)",
16th Annual ACMSIAM Symposium on Discrete Algorithms,
Miami, Florida, USA
(Jan 24, 2006).
"On the Number of CrossingFree 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 CrossingFree
Configurations on Planar Point Sets",
Discrete and Computational Geometry  Twenty Years Later,
AMSSIAM 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 CrossingFree 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

Graph Theory (English),
T. Szabó;
(VL We1012, UE We1516)
contact assistant: Robert Berke.

Erfüllbarkeit
logischer Formeln (SAT)  Kombinatorik und Algorithmen,
E. Welzl;
(VL Fr1012, UE Fr1314)
contact assistant: Andreas Razen.

Algorithmische Geometrie,
B. Gärtner, M. Hoffmann;
(VL Mo1315, UE Mo1516)
contact assistant: Eva Schuberth.

Informatik (DMATH, DPHYS),
B. Gärtner;
(VL Tu1315, UE Tu1517)
contact assistant: Michael Hoffmann.

Theory of Computing (Theoretische Informatik),
J. Hromkovic, E. Welzl;
(VL Th911 HG F7, Fr810 HG F5, UE We1315)
contact assistant:
Sebastian Seibert.

Seminar zur algorithmischen Geometrie,
B. Gärtner, M. Hoffmann, E. Welzl;
(SE Fr1416 CAB G59).

Seminar der Theoretischen Informatik (Mittagsseminar),
B. Gärtner, St. Gerke, J. Giesen, D. FeichtnerKozlov, M. Hoffmann, A. Steger, T. Szabó, E. Welzl;
(SE Tu1213, Th1213).

Optimization and Applications Seminar,
K. Fukuda, B. Gärtner, P. Kall, D. Klatte, H. Lüthi, M. Morari;
(K Mo1618).
Summer 06

Theoretische Informatik (Kernfach),
J. Matoušek, E. Welzl;
(VL Mo910, Th1416; UE Fr 810&1012)
contact assistants:
Leo Rüst, Philipp Zumstein.

Approximate Methods in Geometry,
B. Gärtner, U. Wagner, E. Welzl;
(VL Tu911, UE Tu1112)
contact assistant: Eva Schuberth.

Extremal Combinatorics (English),
T. Szabó;
(VL Fr1012, UE Fr1314)
contact assistant:
Andreas Razen.

Approximation: Theorie & Algorithmen,
A. Steger, E. Welzl, P. Widmayer;
(VL We1012, UE We1213)
contact assistant:
Patrick Traxler.

Advanced Topics in Discrete Mathematics: Graphs (English),
St. Gerke, A. Steger, T. Szabó;
(SE Mo1315).

Seminar SAT,
T. Szabó, E. Welzl;
(SE Th1012)
contact assistant: Dominik Scheder.

Seminar der Theoretischen
Informatik (Mittagsseminar),
B. Gärtner, St. Gerke, D. FeichtnerKozlov, M. Hoffmann, A. Steger, T. Szabó, U. Wagner, E. Welzl;
(SE Tu1213, Th1213).

Optimization and Applications Seminar,
K. Fukuda, B. Gärtner, P. Kall, D. Klatte, H. Lüthi, M. Morari;
(K Mo1618).
Organization of Workshops etc.

Complexity of Games, Polyhedra and Lattice Points
FIM Workshop (Institute for Mathematical Research),
ETH Zurich, Switzerland,
May 1719, 2006,
(I. Bárány, K. Fukuda, H.J. Lüthi and E. Welzl)

4th Gremo Workshop on Open Problems 2006,
Wislikofen, Switzerland,
July 34, 2006,
(Michael Hoffmann, Eva Schuberth)

14th Annual European Symposium on Algorithms (ESA),
ETH Zurich, Switzerland,
September 1115, 2006,
(M. Hoffmann, A. Steger, E. Welzl, P. Widmayer)
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)
/
Coreferees: Lars Engebretsen, Google Switzerland GmbH; Emo Welzl
/
Defense: Aug 21, 2006

Dieter Mitsche,
Spectral Methods for Reconstruction Problems
Advisors: Joachim Giesen, Emo Welzl (referee)
/
Coreferees: 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,
kWise Intersection Theorems
Advisor: T. Szabo
/ 5.7.2006

Anshul Gandhi,
Perfectly Centered Neighborly Polytopes
Advisor: U. Wagner
/ 5.7.2006

Dominic Meier,
kSatisfiable 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,
PsychoPhysical 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 34, 2006).
Sixth CzechSlovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 1015, 2006).
Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 1721, 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 1113, 2006).
Y. BRISE
Attended the conferences/courses/workshops:
Algorithms for the SAT problem, HumboldtUniversität Berlin, Germany (Oct 2729, 2006).
K. FISCHER
Teach. Assistance Informatik (DMATH, DPHYS) (WS05/06).
K. FUKUDA
Courses taught:
"PredocCourse: 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 PointBased Graphics,
Boston, USA (2006)
M. HOFFMANN
Teach. Assistance Informatik (DMATH, DPHYS) (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 1113, 2006).
L. RÜST
Teach. Assistance Digitales Publizieren I: Farbwiedergabe (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Webmaster wwwgremo.
Attended the conferences/courses/workshops:
Summer School on Game Theory, University of Aarhus, Denmark (Jun 2630, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 1113, 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 2029, 2006).
Attended the conferences/courses/workshops:
IS&T/SPIE 18th Annual Symposium on Electronic Imaging,
San Jose, USA (Jan 1519, 2006).
Latin American Theoretical Informatics Symposium (LATIN),
Valdivia, Chile (Mar 2024, 2006).
DIMACS Workshop on Polyhedral Combinatorics of Random Utility,
DIMACS center, Rutgers University, New Jersey (May 2426, 2006).
14th European Signal Processing Conference (EUSIPCO),
Florence, Italy (Sep 48, 2006).
P. TRAXLER
Teach. Assistance Approximation: Theorie & Algorithmen (SS06).
E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.
ViceChair, Department of Computer Science, ETH Zurich (until Sep 30).
Program committee member of

33rd International Colloquium on Automata, Languages and Programming (ICALP `06),
S. Servolo, Venice, Italy
(Jul 9  16, 2006)

(core member of the panel for) Section 15,
"Mathematical Aspects of Computer Science",
International Congress of Mathematicians (ICM),
Madrid, Spain
(Aug 22  30, 2006)

Workshop on Geometric and Topological Combinatorics,
satellite conference of ICM 2006 Alcalá de Henares, Madrid, Spain
(Aug 31Sep 5, 2006)
Editorial Board member of

Discrete and Computational Geometry,
(J. Goodman & R. Pollack, Eds.),
Springer Verlag

Computational Geometry  Theory and Applications,
(K. Mehlhorn & J.R. Sack, Eds.),
Elsevier Science Publishers

Journal for Universal Computer Science,
(H. Maurer, Ed.),
Springer Verlag (electronic journal)

Fundamenta Informaticae,
(Annales Societatis Mathmaticae Polonae, A. Skowron, Ed.),
IOS Press

ORDER,
(W.T. Trotter, Ed.),
Kluwer Academic Press
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 1113, 2006).
Algorithms for the SAT problem, HumboldtUniversität Berlin, Germany (Oct 2729, 2006).
