Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
|
Institut für Theoretische Informatik Departement Informatik ETH Zürich CH-8092 Zürich |
phone +41-1-632 73 92 fax +41-1-632 11 72 |
| Quick Links: | Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Semester Theses, Miscellaneous |
Fukuda, Komei
(1/3 appointment)
Jiří Matoušek (Apr 1 - Jun 30)
Welzl, Emo
Adamy, Udo
(until Feb 29)
Berke, Robert
Csorba, Péter
(Graduate Program CGC)
Fischer, Kaspar
(Graduate Program CGC)
Gärtner, Bernd, Dr.
Giesen, Joachim, Dr.
Hoffmann, Michael
Mitsche, Dieter
Moriyama, Sonoko (until Feb 20)
Okamoto, Yoshio
(Graduate Program CGC)
Rüst, Leo (since Mar 22)
Schuberth, Eva (since Jun 1)
Schurr, Ingo
(Graduate Program CGC, until Sep 30)
Smorodinsky, Shakhar, Dr. (Feb 15 - Oct 31)
Spalinger, Simon (until Jun 30)
Stojakovic, Milos
(Graduate Program CGC)
Szabó, Tibor, Dr.
Wessendorp, Frans (since May 1)
Hefti-Widmer, Franziska
Bettina Speckmann,
Technische Universiteit Eindhoven, The Netherlands (Jan 24 - 29)
The Zigzag Path of a Pseudo-Triangulation
(Mittagsseminar,
Jan 27, 2004)
Zsolt Katona,
Eötvös Lorand University, Budapest (Mar 23)
Width of a scale-free tree
(Mittagsseminar,
Mar 23, 2004)
Uli Wagner, Charles University, Prague (Mar 15 - 19, Apr 13 - 23, May 4 - 9, Sep 27 - Oct 15)
On Halving Simplices in 4 Dimensions (Parts I and II)
(Mittagsseminar,
Mar 16 and 18, 2004)
Andreas Paffenholz, Berlin Technical University, Germany (Apr 1 - Aug 31)
New Polytopes derived from Products
(Mittagsseminar,
Apr 13, 2004)
Gyula Károlyi, Eötvös University
Erdös-Szekeres theorem with forbidden order types
(Mittagsseminar,
Apr 29, 2004)
Pavel Valtr, Charles University, Prague (May 23 - Jun 10)
Strictly convex norms allowing many unit distances
(Mittagsseminar,
May 27, 2004)
Open caps and cups in planar point sets
(Mittagsseminar,
Jun 1, 2004)
Petr Skovron, Charles University, Prague (Jun 1 - 25)
Abstract Models of Optimization Problems
(Mittagsseminar,
Jun 10, 2004)
Carsten Lange, Berlin Technical University, Germany (May 27 - 28)
On generalised Kneser colouring theorems (Mittagsseminar,
May 28, 2004)
Takeaki Uno, National Institute of Informatics (NII) of Japan (Jun 23 - Jul 2)
Efficient Maximal Clique Enumeration and its Application to Frequent Set Mining Problem
(Mittagsseminar,
Jun 24, 2004)
Csaba D. Tóth, Univ. of California at Santa Barbara, USA (Jun 29 - Jul 2)
Binary space partitions of orthogonal subdivisions
(Mittagsseminar,
Jul 1, 2004)
Volker Kaibel, Berlin Technical University, Germany (Jul 24 - 31)
Low-dimensional faces of random 0/1-polytopes
(Mittagsseminar,
Jul 27, 2004)
József Balogh, The Ohio State University, USA (Aug 29 - Sep 5)
The Klee-Minty random edge chain moves with linear speed
(Mittagsseminar,
Aug 31, 2004)
Micha Sharir, Tel Aviv University, Israel (Sep 21 - 27)
On Empty Convex Polygons in a Planar Point Set
(Mittagsseminar,
Sep 23, 2004)
Alexander Gloye, Berlin Free University, Germany (Oct 14)
FU FIGHTERS - An Adaptive Multilayered Platform for Soccer Playing
(Mittagsseminar,
Oct 14, 2004)
Kazuhisa
Makino, Osaka University, Japan (Nov 1-5)
On Computing all Abductive Explanations from a Propositional Horn Theory
(Mittagsseminar,
Nov 2, 2004)
Michael Krivelevich, Tel Aviv University, Israel (Nov 4-9)
Sphere packing in Rn through Graph Theory
(Mittagsseminar,
Nov 9, 2004)
László Lovász, Microsoft Corporation, USA and
Eötvös University, Budapest, Hungary (Nov 17)
The Distance of two Graphs
(Mittagsseminar,
Nov 17, 2004)
(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)
(European Project.)
The project intends to revisit the field of computational geometry
in order to understand how structures that are well-known for linear
objects behave when defined on curves and surfaces. We will consider
the main geometric structures like Voroni diagrams, arrangements and
Minkowski sums, study their mathematical properties, and design
algorithms to construct such structures. To ensure the effectiveness
of our algorithms, we will precisely specify what are the basic numerical
primitives that need to be performed, and consider tradeoffs between
the complexity of the algorithms (i.e. the number of primitive calls)
and the complexity of the primitives and their numerical stability.
Working out carefully the algebraic and robustness issues are two
central objectives of the project. Another major objective is to
integrate the various techniques developed in the project (e.g.
algebra, arithmetics), to compare experimentally various approaches
(e.g. exact versus approximate), and to provide complete solutions
for some fundamental problems.
At site Zurich we focus on surface reconstruction and several
aspects of optimization within the project.
(Coordinator: J. Giesen)
(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 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 other proximity
data structures.
(Contact: J.
Giesen)
(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ó)
(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, ETHZ, and K. Simon, EMPA)
(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)
(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).
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, and
R. Thomas, University of Washington)
G.M. Beutler, J. Kurmanavicius, M. Hoffmann, E. Welzl, R. Huch, M. Bajka, New nomogram for foetal weight estimation based on Hadlock's two-parameter formula, Ultraschall in der Medizin 25 (2004) 1-7.
M. Cieliebak, Th. Erlebach, Zs. Lipták, J. Stoye, E. Welzl, Algorithmic complexity of protein identification: Combinatorics of weighted strings, Discrete Applied Mathematics 137 (2004) 27-46 (Special Issue on Combinatorics of Searching, Sorting, and Coding).
P. Csorba, C. Lange, I. Schurr, A. Waßmer, Box complexes, neighborhood complexes, and the chromatic number, Journal of Combinatorial Theory: Series A 108 (2004) 159-168.
K. Fischer, B. Gärtner, The smallest enclosing ball of balls: combinatorial structure and algorithms, International Journal of Computational Geometry & Applications 14:4/5 (2004) 341-378.
K. Fukuda, From the zonotope construction to the Minkowski addition of convex polytopes, Journal of Symbolic Computation 38 (2004) 1261-1272.
B. Gärtner, J. Solymosi, F. Tschirschnitz, P. Valtr, E. Welzl, One line and n points, Random Structures & Algorithms 23:4 (2004) 453-471.
J. Giesen, M. John, M. Stöcklin, Symmetry of flow diagrams derived from weighted points in the plane, International Journal of Computational Geometry and Applications 13 (2004) 327-337.
J. Giesen, U. Wagner, Shape dimension and intrinsic metric from samples of manifolds, Discrete & Computational Geometry 32:2 (2004) 245-267.
M. Krivelevich, B. Sudakov, T. Szabó, Triangle factors in pseudo-random graphs, Combinatorica 24 (2004) 403-426.
L. Lovász, K. Vesztergombi, U. Wagner, E. Welzl, Convex quadrilaterals and k-sets, in: Towards a Theory of Geometric Graphs (J. Pach, Ed.), AMS Contemporary Mathematics 342 (2004) 139-148.
J. Matousek, A combinatorial proof of Kneser's conjecture, Combinatorica 24 (2004) 163-170.
J. Matousek, U. Wagner, New constructions of weak epsilon-nets, Discrete & Computational Geometry 32:2 (2004) 195-206.
Y. Okamoto, Traveling salesman games with the Monge property, Discrete Applied Mathematics 138 (2004) 349-369.
I. Schurr, T. Szabó, Finding the sink takes some time, Discrete & Computational Geometry 31 (2004) 627-642.
M. Sharir, E. Welzl, Point-line incidences in space, Combinatorics, Probability and Computing 13 (2004) 203-220.
Cs. D. Tóth, Illuminating Labyrinths, Discrete Applied Mathematics 138 (1-2) (2004) 215-228.
U. Adamy, Th. Erlebach, Online coloring of intervals with bandwidth, Proc. 1st Workshop on Approximation and Online Algorithms (WAOA03), Lecture Notes in Computer Science 2909 (2004) 1-12.
U. Adamy, M. Hoffmann, J. Solymosi, M. Stojakovic, Coloring Octrees, Proc. 10th Int. Computing and Combinatorics Conference (COCOON'04), Lecture Notes in Computer Science 3106 (2004) 62-71.
P.K. Agarwal, M. Sharir, E. Welzl, Algorithms for Center and Tverberg Points, Proc. 20th Annual ACM Symposium on Computational Geometry (SoCG) (2004) 61-67.
M. Andersson, J. Giesen, M. Pauly and B. Speckmann, Bounds on the k-neighborhood for locally uniform sampled surfaces, Proc. 1st Symposium on Point Based Graphics (PBG`04) (2004) 167-171.
Th. Bietenhader, Y. Okamoto, Core stability of minimum coloring games, Proc. 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04), Lecture Notes in Computer Science 3353 (2004) 389-401.
E.D. Demaine, M. Hoffmann, M. Holzer, PushPush-k is PSPACE-Complete, Proc. 3rd International Conference on Fun with Algorithms (FUN`04) (2004) 159-170.
V.G. Deineko, M. Hoffmann, Y. Okamoto, G.J. Woeginger, The Traveling Salesman Problem with few inner points, Proc. 10th International Computing and Combinatorics Conference (COCOON'04), Lecture Notes in Computer Science 3106 (2004) 268-277.
T.K. Dey, J. Giesen, S. Goswami, Shape segmentation and matching from noisy point clouds, Proc. 1st Symposium on Point Based Graphics (PBG`04) (2004) 193-199.
K. Fukuda, B. Kaluzny, The criss-cross method can take Omega(n^d) pivots, Proc. 20th Annual ACM Symposium on Computational Geometry (SoCG) (2004) 401-408.
K. Fukuda, V. Rosta, Exact parallel algorithms for the location depth and the maximum feasible subsystem problems, in Frontiers in global optimization (C.A. Floudas, P.M. Pardalos, Eds.), Nonconvex Optim. Appl. 74 (2004) 123-133, Kluwer Acad. Publ., Boston, MA.
R. Haas, M. Hoffmann, Chordless paths through three vertices, Proceedings of 1st International Workshop on Parameterized and Exact Computation (IWPEC'04), Lecture Notes in Computer Science 3162 (2004) 25-36.
M. Hoffmann, Y. Okamoto, The minimum weight triangulation problem with few inner points, Proceedings of 1st International Workshop on Parameterized and Exact Computation (IWPEC'04), Lecture Notes in Computer Science 3162 (2004) 200-212.
M. Hoffmann, B. Speckmann, and Cs.D. Tóth, Pointed Binary Encompassing Trees, Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT`04), Lecture Notes in Computer Science 3111 (2004) 442-454.
J. Matoušek, T. Szabó, RANDOM EDGE can be exponential on abstract cubes, Proc. 45nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS) (2004) 92-100.
R. Pinchasi, S. Smorodinsky, On Locally Delaunay Geometric Graphs, Proc. 20th Annual ACM Symposium on Computational Geometry (SoCG) (2004) 378-382.
B. Schoelkopf, J. Giesen, S. Spalinger, Kernel methods for implicit surface modeling, Proc. 18th Annual Conference on Neural Information Processing Systems (NIPS) (2004) 1193-1200.
M. Dyer, N. Megiddo, E. Welzl, Linear Programming, in: Handbook of Discrete and Computational Geometry (J.E. Goodman, J. O'Rourke, eds.), Chapman and Hall/CRC, (2004) 999-1014.
J. Giesen, S. Spalinger, Meshless Surface Reconstruction by Kernel Clustering, Proc. 16th Candian Conference on Computational Geometry (CCCG) (2004) 11-14.
M. Hoffmann, Cs. D. Tóth, Pointed Binary Encompassing Trees: Simple and Optimal, Abstracts 14th Annual Fall Workshop on Computational Geometry (2004) 28-29.
P. CSORBA
"On box complexes", MittagsSeminar, Berlin University of Technology,
Germany (Mar 11, 2004),
"Homotopy types of box complexes",
Algebraic Topological Methods in Computer Science, II,
University of Western Ontario,
London, Canada,
(Jul 18, 2004).
"Homotopy types of box complexes",
4th Annual Workshop on Combinatorics, Geometry, and Computation
(CGC),
Stels, Switzerland
(Oct 6, 2004).
K. FISCHER
"Miniball-of-balls in subexponential time",
4th Annual Workshop on Combinatorics, Geometry, and Computation
(CGC),
Stels, Switzerland
(Oct 5, 2004).
K. FUKUDA
"Old and new ideas of constructing non-representable oriented matroids",
Seminar, Equipe Combinatoire,
University of Paris 6, France, (May 13, 2004).
"On the connectivity of the flip graph of acyclic orientations",
Seminar, Equipe Combinatoire,
University of Paris 6, France, (Jun 3, 2004).
Drawing and Building Polytopes,
Model Building Party, Geometric Combinatorics, PCMI/IAS, Park City, Utah, (Jul 13, 2004).
"Old and new ideas of constructing non-representable oriented matroids",
Research Program Talk, Geometric Combinatorics, PCMI/IAS, Park City, Utah, (Jul 19, 2004).
"Generating all vertices in implicitly defined polyhedra",
Veszprém Optimization Conference: Advanced Algorithms (VOCAL), Veszprém, Hungary,
(Dec 14, 2004; plenary talk).
B. GÄRTNER
"Unique Sink orinetations of Grids",
4th Annual Workshop on Combinatorics, Geometry, and Computation
(CGC),
Stels, Switzerland
(Oct 6, 2004).
J. GIESEN
"Surface Reconstruction: Progress Report on WP 4.2",
ECG Final Workshop, Paris, France (Apr 1, 2004).
"Surface Reconstruction within ECG", ECG Review Meeting, Brussels, Belgium
(Jun 23, 2004).
"Induced Flows and Applications", TU Eindhoven, The Netherlands (Jun 22,
2004).
"Bounds on the k-neighborhood for locally uniform sampled surfaces", Symposium
on Point Based Graphics, Zürich, Switzerland (Jun 4, 2004).
"Shape segmentation and matching from noisy point clouds", Symposium
on Point Based Graphics, Zürich, Switzerland (Jun 4, 2004).
"Induced Flows and Applications",
University of Illinois at Urbana-Champaign,
USA (Oct 6, 2004).
"Induced Flows and Applications",
Max-Planck-Institut für Informatik Saarbrücken, Germany
(Sep 27, 2004).
M. HOFFMANN
"Chordless Paths through Three Vertices",
Upper Rhine Algorithms Workshop (URAW),
Karlsruhe University,
Germany (Mar 19, 2004).
"Pointed Binary Encompassing Trees",
9th Scandinavian Workshop on Algorithm Theory (SWAT),
Louisiana Museum of Modern Art, Humlebaek, Denmark,
(Jul 10, 2004).
"Chordless paths through three vertices",
1st International Workshop on Parameterized and
Exact Computation (IWPEC'04),
Bergen, Norway (Sep 15, 2004).
Y. OKAMOTO
"The Affine Representation Theorem for Abstract Convex Geometries",
2004 Barbados Undercurrent Workshop
Barbados Undercurrent Workshop "Polyhedra, Convex Geometry and
Optimization", Bellairs Research Institute of McGill University,
Holetown, Barbados,
(Mar 8, 2004).
"The Traveling Salesman Problem with Few Inner Points",
Upper
Rhine Algorithms Workshop (URAW),
Karlsruhe University,
Germany (Mar 19, 2004).
"The minimum weight triangulation problem with few inner points",
1st International Workshop on Parameterized and
Exact Computation (IWPEC'04),
Bergen, Norway
(Sep 16, 2004).
"Core stability of minimum coloring games",
30th
International Workshop on Graph-Theoretic Concepts in
Computer Science (WG),
Physikzentrum Bad Honnef, Bad Honnef, Germany,
(Jun 23, 2004).
"Polytopal digraphs" (in Japanese),
5th Combinatorics Young Summer Seminar,
Kemigawa Seminar House, University of Tokyo, Chiba, Japan,
(Aug 13, 2004).
"The traveling salesman problem with few inner points",
10th International
Computing and Combinatorics Conference (COCOON),
Jeju Island, Korea,
(Aug 18, 2004).
"Revenue maximizing auctions (2)",
GI-Dagsthul-Seminar
"Game-Theoretic Analyses of the Internet",
Schloss Dagstuhl, Wadern, Germany,
(Sep 1, 2004).
"The minimum weight triangulation problem with few inner points",
1st International
Workshop on Parameterized and Exact Computation (IWPEC),
Bergen, Norway,
(Sep 16, 2004).
"The minimum weight triangulation problem with few inner points"
(in Japanese),
University of Tokyo, Tokyo, Japan,
(Sept 22, 2004).
"Fast exact algorithms for discrete optimization" (in Japanese),
Combinatorial Optimization Seminar,
Miura Kaigan, Yokosuka, Japan,
(Sep 23, 2004).
"The traveling salesman problem with few inner points" (in Japanese),
Tohoku University,
(Sep 29, 2004).
"The minimum weight triangulation problem with few inner points,"
4th Annual Workshop on Combinatorics, Geometry, and Computation
(CGC),
Stels, Switzerland
(Oct 5, 2004).
E. SCHUBERTH
"Geometrische Ansätze im gamut mapping", EMPA, St. Gallen,
Switzerland (Nov 2, 2004).
I. SCHURR
"Memoryless Algorithms on Unique Sink Orientations of Cubes",
Upper
Rhine Algorithms Workshop (URAW),
Karlsruhe University,
Germany
(Mar 20, 2004).
SH. SMORODINSKY
"On Conflict-Free Colorings",
UPC Computational Geometry Seminar,
Barcelona, Spain
(May 19, 2004).
"On Locally Delaunay Geometric Graphs",
20th ACM Symposium on Computational Geometry (SoCG),
Polytechnic University brooklyn, New York, USA
(Jun 11, 2004).
"On Locally Delaunay Geometric Graphs",
Computer Science Theory Lunch,
Berkeley, California, USA
(Sep 15, 2004).
S. SPALINGER
"Support Vector Clustering for Surface Reconstruction",
ECG Final Workshop, Paris, France
(Apr 1, 2004).
"Meshless Surface Reconstruction by Kernel Clustering",
16th Candian Conference on Computational Geometry (CCCG),
Concordia University, Montreal,
Canada
(Aug 9, 2004)
M. STOJAKOVIC
"Positional Games On Random Graphs", SLADIM Seminar, Department of
Mathematics and Computer Science, Novi Sad (Mar 31, 2004).
"Positional Games On Random Graphs", GTA Seminar, Mathematical
Institute SANU, Belgrade (May 4, 2004).
"Coloring Octrees", 10th International Computing and Combinatorics Conference (COCOON 2004),
Jeju Island, Korea, (Aug 18, 2004).
"Positional Games On Random Graphs", Combinatorics '04 Conference, Capomulini, Italy, (Sep 16, 2004).
T. SZABÓ
"Independent Transversals in r-Partite Graphs and Related
Extremal Problems",
Charles University, Prague
(Feb 26, 2004).
"Unique Sink Orientation of Cubes - Motivation and Algorithms"
(two tutorials),
Barbados Undercurrent Workshop "Polyhedra, Convex Geometry and
Optimization", Bellairs Research Institute of McGill University,
Holetown, Barbados,
(Mar 9 and 10, 2004).
"Independent Transversals in r-Partite Graphs and
Related Extremal Problems",
Tel Aviv University, Combinatorics Seminar, Tel Aviv, Israel
(May 16, 2004).
"Unique Sink Orientation of Cubes - Motivation and Algorithms",
EPFL, Operations Research Reminar, Lausanne, Switzerland,
(Apr 30, 2004).
"Induced matching transversals and m-connectedness",
Geometry,
Topology, and Combinatorics,
KTH Stockholm, Sweden
(Jul 3, 2004).
"Odd independent transversals are odd",
Combinatorics Seminar, Rényi Institute, Budapest, Hungary
(Sep 23, 2004).
"RandomEdge can be exponential on abstract cubes",
45nd Ann. IEEE Symp. on Foundations of Computer Science
(FOCS), Rome, Italy
(Oct 17, 2004).
E. WELZL
"Geometric Optimization and Unique Sink Orientations of Cubes",
29th International
Symposium on Mathematical Foundations of Computer
Science (MFCS),
Prague, Czech Republic
(Aug 27, 2004; invited talk)
Approximation: Theory and Algorithms, M. Cochand, T. Erlebach, B. Gärtner, A. Steger, P. Widmayer.
Erfüllbarkeit logischer Formeln (SAT) - Kombinatorik und Algorithmen, E. Welzl; contact assistant: Milos Stojakovic.
Seminar der Theoretischen Informatik (Mittagsseminar), B. Gärtner, J. Giesen, T. Szabó, E. Welzl.
Theoretische Informatik (Kernfach), Jiří Matoušek, E. Welzl; contact assistant: Ingo Schurr/Robert Berke.
Informatik II (D-MATH), J. Giesen.
Algorithmische Geometrie, B. Gärtner, Riko Jacob; contact assistant: Michael Hoffmann.
Extremal Combinatorics Seminar (in English), T. Szabó.
Seminar Algorithmische Geometrie & Computergraphik, J. Giesen, M. Gross, E. Welzl.
Seminar der Theoretischen Informatik (Mittagsseminar), B. Gärtner, J. Giesen, T. Szabó, E. Welzl.
Optimization Seminar, K. Fukuda, F. Chudak.
22nd CGAL Design and Implementation Meeting, International Conference and Research Center for Computer Science (IBFI) , Schloss Dagstuhl, Germany, Jan 4-9, 2004, (Michael Hoffmann)
Undercurrent Workshop on Polyhedral Computation, Bellairs Research Institute, Barbados, March 7-14, 2004, (Komei Fukuda)
Mathematical Aspects of Theoretical Computer Science, ETH Zurich (FIM), May 24-26, 2004 (Béla Bollobás, Maurice Cochand, Angelika Steger, Jiří Matoušek)
2nd Gremo Workshop on Open Problems 2004 , Cumpadials, Switzerland, July 4-8, 2004, (Michael Hoffmann, Ingo Schurr)
4th Workshop on Combinatorics, Geometry, and Computation (CGC), Hof de Planis, Stels, Switzerland, October 4-7, 2004, (Michael Hoffmann)
Ingo Schurr,
Unique Sink Orientations of Cubes
Advisors: Tibor Szabó (co-referee), D-INFK, ETH Zurich, Emo Welzl (referee)
/
Co-referee: Günter Ziegler, TU Berlin
/
Defense: Oct 4, 2004
Thomas Bietenhader,
Core stability of minimum coloring games
Advisor: Y. Okamoto
/
11.3.2004.
Stefan Feistenauer,
Interpolating images with the adaptive neighborhood graph
Advisor: J. Giesen
/
15.2.2004.
Isha Geigenfeind,
Implementation of miniball-of-balls using USO-algorithms
Advisor: K. Fischer
/
29.3.2004.
Tobias Gysi,
Efficient generation of the hamiltonian paths in cocomparability graphs
Advisor: Y. Okamoto
/
21.10.2004.
Mélanie Raemy,
Approximation algorithms for matroids
Advisor: Y. Okamoto
/
10.9.2004.
Stefano Tessaro,
Randomized algorithms to locate the sink in low dimensional
unique sink orientations of cubes
Advisors: I. Schurr, T. Szabó
/
22.10.2004.
U. ADAMY
Teach. Assistance Logik (WS03/04).
Coordinator Mittagsseminar (until Feb 29).
R. BERKE
Teach. Assistance Information und Kommunikation (WS03/04).
Teach. Assistance Theoretische Informatik (Kernfach) (SS04).
P. CSORBA
Teach. Assistance Randomized Algorithms (WS03/04).
Attended "Kombinatorische Geometrie I: Diskrete Geometrie"
(by G. Ziegler),
part of the Prag-Berlin "DocCourse"-Program.
Attended the workshop
"Combinatorial Aspects of Hyperplane Arrangements",
part of MSRI's Special Semester in Hyperplane Arrangements and Applications,
(Nov 1-5, 2004).
K. FISCHER
Teach. Assistance Informatik I (D-BAUG) (WS03/04).
K. FUKUDA
B. GÄRTNER
Program committee member of
The 21th International Symposium on Theoretical Aspects of Computer Science (STACS'04), Montpellier, France (Mar 25-27, 2004)
The 20th Annual ACM Symposium on Computational Geometry (SoCG'04), Brooklyn, New York, USA (Jun 9-11, 2004)
J. GIESEN
Program committee member of
Symposium on Point-Based Graphics, Zurich, Switzerland (Jun 2-4, 2004)
M. HOFFMANN
Teach. Assistance Algorithmische Geometrie (SS04).
Informatik Koordinator.
Member of the CGAL Editorial Board.
D. MITSCHE
Coordinator Mittagsseminar (since March 1).
Teach. Assistance Logik (WS03/04).
Teach. Assistance Informatik II (D-MATH) (SS04).
Y. OKAMOTO
Teach. Assistance Graph Theory (WS03/04).
Teach. Assistance Theoretische Informatik (Kernfach) (SS04).
Graduate Summer School on Geometric Combinatorics,
IAS/Park City Mathematics Institute Annual Summer Session 2004,
Park City, UT, USA, (Jul 11-31, 2004).
GI-Dagstuhl-Seminar: Game-Theoretic Analyses of the Internet
Schloss Dagstuhl, Germany,
(Aug 30-Sep 3, 2004).
L. RÜST
Teach. Assistance Theoretische Informatik (Kernfach) (SS04).
I. SCHURR
Teach. Assistance Theoretische Informatik (Kernfach) (SS04).
S. SPALINGER
Teach. Assistance Computational Marketing (WS03/04).
Teach. Assistance Informatik II (D-MATH) (SS04).
M. STOJAKOVIC
Teach. Assistance Satisfiability of Boolean Formulas - Combinatorics and Algorithms (WS03/04).
E. WELZL
Speaker (for site Zurich) of Berlin-Zurich Graduate Program `Combinatorics,
Geometry, and Computation'.
Head of Institute of Theoretical Computer Science, ETH Zurich.
Vice-Chair (Resources), Department of Computer Science, ETH Zurich (since Oct 1, 2004).
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
Assistant Professor in Computer Science (Interactive Multimedia), Department of Computer Science
Professorship in Statistics, Department of Mathematics (chair)
Full Professor/Assistant Professor (Tenure Track) of Ecosystem Management, Department of Environmental Sciences (chair)
Member of the EATCS Council (European
Association for Theoretical Computer Science).
Member of EATCS Awards Committee; with Jean-Pierre Jouannoud and Jan van Leeuwen (chair).
Member of expert panel, program "Basic Research in Programming,
Algorithms and their Support Functions" for Academy of Finland.
Member of "Prüfungsgruppe zur Begutachtung des Einrichtungsantrages für ein
internationales Graduiertenkolleg" for German Research Society (DFG).
Mitglied des Fachausschusses 0.1. Theoretische Informatik der
Gesellschaft für Informatik (GI).
Gutachter für Deutsche Forschungsgemeinschaft (DFG),
Graduiertenkollegs.
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.
