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 |
Personnel
Fukada, Komei (1/3 appointment, since Oct 1)
Welzl, Emo
Adamy, Udo
Berke, Robert
(since Oct 13)
Csorba, Péter
(Graduate Program CGC)
Fischer, Kaspar
(Graduate Program CGC)
Gärtner, Bernd, Dr.
Giesen, Joachim, Dr.
Hoffmann, Michael
John, Matthias,
(until Sep 30)
Mitsche, Dieter,
(since Jun 1)
Moriyama, Sonoko (since Oct 1)
Okamoto, Yoshio (Graduate Program CGC)
Schurr, Ingo (Graduate Program CGC)
Spalinger, Simon
(since Oct 20)
Speckmann, Bettina, Dr.
(Post-Doc in Graduate Program CGC,
until May 31)
Stojakovic, Milos (Graduate Program CGC)
Szabó, Tibor, Dr.
Tschirschnitz, Falk
(until Sep 30)
Wagner, Uli
(until Jul 31)
Hefti-Widmer, Franziska
Guests
József Beck, Rutgers University, New Brunswick, New Jersey, USA
(Jan 6 - Feb 28)
Positional Games
(Pre-Doc Course, Thursdays and Fridays,
Jan 6 - Feb 7, 2003)
Arnold Wassmer,
Berlin University of Technology, Berlin, Germany
(Jan 9 - Apr 4, visiting, Graduate Program CGC)
The Hom Complex
(Mittagsseminar,
Apr 3, 2003)
Ron Aharoni, Technion, Israel
(Jan 20 - 22)
Independent Systems of Representatives
(Mittagsseminar,
Jan 21, 2003)
Jiri Matousek,
Charles University, Prague, Czech Republic
(Feb 3 - 9)
Crossing Number and Small Nonplanar Subgraphs,
(Mittagsseminar,
Feb 7, 2003)
Marc van Kreveld,
Utrecht University,
The Netherlands (Feb 3 - 7)
Composable Art and Combinatorics,
(Mittagsseminar,
Feb 6, 2003)
Michael Krivelevich, Tel Aviv University, Israel
(Feb 9 - 14)
Turan Numbers of Bipartite Graphs and Related Questions
(Mittagsseminar,
Feb 11, 2003)
Christoph Ambühl,
Università degli Studi di Roma Tor Vergata, Italy
(Feb 9 - 14)
Oswin Aichholzer, Graz University of Technology, Austria
(Feb 10 - 17)
Playing with Triangulations (Mittagsseminar, Feb 13, 2003)
Riko Jacob, Ludwig-Maximilians-University, Munich, Germany
(Mar 5 - 7)
Amortized Optimal Dynamic Planar Convex Hull by Querying (Mittagsseminar,
Mar 3, 2003)
Martin Kutz, Berlin, Free University, Germany (Mar 10 - Apr 2)
Gyula Károlyi,
Eötvös University, Budapest, Hungary (Mar 20)
The Erdös-Heilbronn Problem in Abelian Groups(Mittagsseminar,
Mar 20, 2003)
Csaba Dávid Tóth, University of California at Santa Barbara, USA (Mar 27 - 28)
Total Latency and Selfish Behavior in P2P Data-Sharing Systems
(Mittagsseminar, Mar 27, 2003)
Penny Haxell, University of Waterloo, Canada (Apr 9 - May 5)
Strong Coloring and Related Problems (Mittagsseminar, Apr 22, 2003)
Grzegorz Rozenberg,
Leiden Institute of Advanced Computer Science (LIACS),
Leiden Center for Natural Computing (LCNC),
Leiden University, The Netherlands, and University of Colorado at Boulder, USA
(May 2-7)
Gene Assembly in Ciliates - a Splendid Example of Natural Computing
(Computer Science Colloquium, May 5, 2003)
Models of Molecular Computing - Formal Models for Gene Assembly (Mittagsseminar, May 6, 2003)
Models of Molecular Computing - Computations Based on Molecular Reactions
(part of Bioinspired Computation and Optimization course, May 6, 2003)
Carsten Lange,
Berlin University of Technology, Berlin, Germany (May 8 - 11)
Anisotropic Fairing of Point Sets
(Mittagsseminar, May 8, 2003)
Jiri Matousek,
Charles University, Prague, Czech Republic
(Jun 1 - 30)
A Briefing on Dimension Reduction
(Mittagsseminar,
Jun 16, 2003)
Nina Amenta,
University of California at Davis, California, USA (Jun 17 - 28)
Incremental constructions con BRIO (Mittagsseminar, Jun 19, 2003)
Voronoi Diagrams of Balls (Mittagsseminar, Jun 23, 2003)
Walter Morris,
George Mason University, Fairfax, Virginia, USA (Jun 24 - 26)
Regular crosspolytope-subdivisions and LP-orientations of cubes
(Mittagsseminar,
Jun 24, 2003)
József Solymosi,
University of California at San Diego, California, USA
(Jul 1 - 15)
Products and Incidences
(Mittagsseminar,
Jun 3, 2003)
Csaba David Toth,
University of California at Santa Barbara, California, USA (Jul 8 - 16)
Alternating Paths along Orthogonal Segments
(Mittagsseminar, Jul 15, 2003)
Bettina Speckmann, Technische Universiteit Eindhoven, The Netherlands (Jul 8 - 11)
Shakhar Smorodinski, Tel Aviv University, Israel (Jul 8 - 13)
Subhash Suri,
University of California at Santa Barbara, California, USA (Jul 17)
A Peer Matching Game
(Mittagsseminar,
Jul 17, 2003)
Dirk Nowotka,
University of Turku, Finland (Sep 1 - 5)
Periodicity and Unbordered Words
(Mittagsseminar,
Sep 2, 2003)
Johannes Fischer, Freiburg University, Germany
(Sep 9, 2003)
Version Spaces in Constraint-Based Data Mining
(Mittagsseminar,
Sep 9, 2003)
Heiko Vogler,
Dresden University of Technology, Germany
(Sep 15 - 20)
A Kleene Theorem for Weighted Tree Automata
(Mittagsseminar,
Sep 16, 2003)
Michael Krivelevich, Tel Aviv University, Israel
(Oct 11 - 17)
List Coloring of Graphs
(Mittagsseminar,
Oct 14, 2003)
Rekha R. Thomas, Department of Mathematics, University of Washington
(Nov 24 - 28)
Lattice point free polytopes in integer programming (Optimization Seminar)
(Nov 24, 2003)
Groebner Bases Methods in Integer Programming
(Automatic
Control Laboratory Seminar)
(Nov 26, 2003)
Nico Kruithof,
Institute for Mathematics and Computing Science,
University of Groningen
(Nov 24 - 28)
Approximation by Skin Surfaces
(Mittagsseminar,
Nov 27, 2003)
Eva Schuberth, Passau University, Germany
(Dec 4, 2003)
Formale Spezifikation von Software-Architektur
(Mittagsseminar,
Dec 4, 2003)
Grants
(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 ETH Zurich and German Research Society, DFG.
Starting January 1, 2003, at ETH only running scholarships are
funded up to the end of the originally planed time span, but no other activities.)
Successful scientific interaction between discrete mathematics,
algorithms, and application areas in computer science is
increasing. In particular, combinatorics and discrete geometry
provide the foundations for algorithms in general, and for
combinatorial optimization and computational geometry in
particular.
These fields, in turn, either have direct applications or provide
algorithmic concepts for many application areas such as
optimization, computer graphics and vision, geographic information
systems, robotics, molecular modeling and computer aided design.
This initiative focuses on educating graduate students in the
area where these fields interact. The Pre-Doc Program
constitutes a one-semester exposure to an active research
environment with dedicated research-oriented courses.
The Graduate Program is a joint initiative of the departments
Computer Science, Mathematics and Electrical Engineering at ETH Zurich
with the three
universities in Berlin (and a number of other partner institutions).
The goal is to establish international contacts in both research
and education, and to create a focused program with completion
of a Ph.D. thesis within two and a half years.
(Contact: H. Alt, Berlin, and E. Welzl, ETHZ.)
(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)
Publications
A. Andrzejak, E. Welzl, In between k-Sets, j-Facets, and i-Faces: (i,j)-Partitions, Discrete & Computational Geometry 29:1 (2003) 105-131.
E. D. Demaine, M. L. Demaine, M. Hoffmann, J. O'Rourke, Pushing Blocks is Hard, Computational Geometry - Theory and Applications 26:1 (2003) 21-36.
T.K. Dey, J. Giesen, Detecting undersampling in surface reconstruction, Discrete & Computational Geometry - The Goodman-Pollack Festschrift (2003) 328-345.
T. K. Dey, J. Giesen, S. Goswami, W. Zhao, Shape dimension and approximation from samples, Discrete & Computational Geometry 29:3 (2003) 419-434.
J. Hage, T. Harju, E. Welzl, Euler graphs, triangle-free graphs and bipartite graphs in switching classes, Fundamenta Informaticae 58:1 (2003) 23-37.
P. Haxell, T. Szabó, G. Tardos, Bounded size components - Partitions and Transversals, Journal of Combinatorial Theory (Series B) 88:2 (2003) 281-297.
M. Hoffmann, Cs. D. Tóth, Segment endpoint visibility graphs are Hamiltonian, Computational Geometry - Theory and Applications 26:1 (2003) 47-68.
M. Hoffmann, Cs. D. Tóth, Alternating paths through disjoint line segments, Information Processing Letters 87:6 (2003) 287-294.
K. Kashiwabara, Y. Okamoto, A greedy algorithm for convex geometries, Discrete Applied Mathematics 131:2 (2003) 449-465.
L. Kettner, D. Kirkpatrick, A. Mantler, J. Snoeyink, B. Speckmann, F. Takeuchi, Tight Degree Bounds for Pseudo-Triangulations of Points. Computational Geometry - Theory and Applications 25 (2003) 3-12.
J. Matousek, M. Stojakovic, On restricted min-wise independence of permutations, Random Structures & Algorithms 23 (2003) 397-408.
Y. Okamoto, Some properties of the core on convex geometries, Mathematical Methods of Operations Research 56 (2003) 377-386.
Y. Okamoto, Submodularity of some classes of the combinatorial optimization games, Mathematical Methods of Operations Research 58:1 (2003) 131-139.
Y. Okamoto, M. Nakamura, The forbidden minor characterization of line-search antimatroids of rooted digraphs, Discrete Applied Mathematics 131:2 (2003) 523-533.
J. Pach, J. Solymosi, G. Tóth, Unavoidable Configurations in Complete Topological Graphs, Discrete & Computational Geometry 30 (2003) 311-320.
M. Sharir, E. Welzl, Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem, Discrete & Computational Geometry - The Goodman-Pollack Festschrift (2003) 789-797.
M. Stojakovic, Limit shape of optimal convex lattice polygons in the sense of different metrics, Discrete Mathematics 271 (2003) 235-249.
T. Szabó, On the spectrum of projective norm-graphs, Information Processing Letters 86:2 (2003) 71-74.
T. Szabó, Van H. Vu, Turán's Theorem in sparse random graphs, Random Structures and Algorithms 23:3 (2003) 225-234.
Cs. D. Tóth, Illuminating Disjoint Line Segments in the Plane, Discrete & Computational Geometry 30:3 (2003) 489-505.
Cs. D. Tóth, A Note on Binary Plane Partitions, Discrete & Computational Geometry 30:1 (2003) 3-16.
Cs. D. Tóth, Illumination of Polygons with 45º-Floodlights, Discrete Mathematics 265:1-3 (2003) 251-260.
Cs. D. Tóth, Guarding disjoint triangles and claws in the plane, Computational Geometry - Theory and Applications 25:1-3 (2003) 51-65.
Cs. D. Tóth, Binary Space Partition for Line Segments with a Limited Number of Directions, SIAM Journal of Computing 32:2 (2003) 307-325.
P. Carmi, Th. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 2880 (2003) 143-155.
K. Fischer, B. Gärtner, M. Kutz, Fast smallest-enclosing-ball computation in high dimensions, Proc. 11th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2832 (2003) 630-641.
T.K. Dey, J. Giesen, S. Goswami, Shape segmentation and matching with flow discretization, Proc. 8th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 2748 (2003) 25-36.
T. K. Dey, J. Giesen, M. John, alpha-Shapes and flow shapes are homotopy equivalent, Proc. 35rd Annual ACM Symposium on the Theory of Computing (STOC) (2003) 493-502.
K. Fischer, B. Gärtner, The smallest enclosing ball of balls: combinatorial structure and algorithms, Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG) (2003) 292-301.
J. Giesen, M. John, The flow complex: A data structure for geometric modeling, Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2003) 285-294.
J. Giesen, M. John, Computing the weighted flow complex, Proc. 8th International Fall Workshop Vision, Modeling, and Visualization (2003) 235-243.
J. Giesen, U. Wagner, Shape dimension and intrinsic metric from samples of manifolds with high co-dimension, Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG) (2003) 329-337.
K. Kashiwabara, Y. Okamoto, T. Uno, Matroid representation of clique complexes, Proc. 9th International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science 2697 (2003) 192-201.
J. Matousek, U. Wagner, New constructions of weak epsilon-nets, Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG) (2003) 129-135.
J. Matousek, M. Stojakovic, On restricted min-wise independence of permutations, Abstracts European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB) (2003) 264-268.
Y. Okamoto, Fair cost allocations under conflicts - a game-theoretic point of view, Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 2906 (2003) 686--695.
Y. Okamoto, The free complex of a two-dimensional generalized convex shelling, Abstracts European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB) (2003) 289-293.
B. Speckmann, Cs. D. Tóth, Allocating vertex pi-guards in simple polygons via pseudo-triangulations, Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2003) 109-118.
U. Wagner, On the Rectilinear Crossing Number of Complete Graphs, Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2003) 583-588.
O. Aichholzer, G. Rote, B. Speckmann, I. Streinu, The zigzag path of a pseudo-triangulation, Proc. 8th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 2748 (2003), 377-388.
O. Aichholzer, M. Hoffmann, B. Speckmann, and Cs. D. Tóth, Degree bounds for constrained pseudo-triangulations, Proc. 15th Canadian Conference on Computational Geometry (2003) 155-158.
P. Carmi, Th. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs (in Japanese), Mathematics and Algorithms of Optimization, Surikaisekikenkyusho Kokyuroku 1297 (2002) 12-23.
P. Carmi, Th. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, TIK-Report 155, Computer Engineering and Networks Laboratory (TIK), ETH Zurich (2003).
K. Fischer, B. Gärtner, Cgal-based implementation of smallest enclosing balls of balls, ECG Technical Report No. ECG-TR-121202-01, ETH Zurich (2003).
K. Fischer, B. Gärtner, Prototype implementation of approximate minimum enclosing ellipsoids, ECG Technical Report No. ECG-TR-301211-01, ETH Zurich (2003).
M. Hachimori, Y. Okamoto, Japanese translation of "Lectures on Polytopes" (author: Günter M. Ziegler), Springer-Verlag Tokyo, 2003.
K. Kashiwabara, Y. Okamoto, T. Uno, Matroid representation of clique complexes, Proc. 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (2003) 40-48.
H. Mohri, Y. Okamoto, Discrete optimization and cooperative games (2), (in Japanese), Communications of the Operations Research Society of Japan 48 (2003) 114-120.
Y. Okamoto, Edelman-Reiner's conjecture on the free complex of an abstract convex geometry, (in Japanese) Proc. of Ouyou Suugaku Goudou Kenkyuu Shuukai (2003) 125-128.
Lectures
U. ADAMY
"Call Admission Control in Star Networks",
Dagstuhl Seminar on Algorithmic Aspects of Large and
Complex Networks,
Schloss Dagstuhl, Germany (Sep 4, 2003).
"On-line Coloring of Intervals with Bandwidth",
First Workshop on Approximation and Online Algorithms (WAOA),
Budapest, Hungary (Sep 17, 2003).
P. CSORBA
"Topological Methods in Combinatorics and Geometry", Arbeitsgemeinschaft
Topology and Robotics,
Zürich
(Jan 8, 2003).
"Topological Lower Bound for the Chromatic Number", The 7th School of
Mathematics on "Combinatorics, Topology and Convexity: Their Meeting
Points",
Jerusalem
(Apr 27, 2003).
"On the n-in-a-row Game",
3rd Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Neustrelitz, Germany
(Sep 29, 2003).
K. FISCHER
"The smallest enclosing ball of balls:
combinatorial structure and
algorithms",
19th
Annual ACM Symposium on Computational Geometry (SoCG),
San Diego USA,
(Jun 10, 2003).
"Review of ECG software-related work at ETHZ",
ECG General Workshop,
FU Berlin, Germany
(Jun 25, 2003).
"Unique sink orientations from miniball-of-balls",
3rd Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Neustrelitz, Germany
(Sep 30, 2003).
B. GÄRTNER
"Digraphs of (d,d+2)-polytopes",
Bellairs Undercurrent Workshop on Polytopes,
Games and Matroids,
Barbados
(Mar 13, 2003).
"LP-type problems - Geometrische Optimierung zwischen Theorie und Praxis",
Konstanz University, Germany (Mar 17, 2003).
"LP-type problems: an abstract framework with concrete applications",
London School of Economics, London, UK (May 28, 2003)
"Linear Algebra and LP-Type Problems",
Mathematical
Foundations of Geometric Algorithms,
Mathematical Sciences Research Institute (MSRI),
Berkeley, California, USA
(invited, Oct 15, 2003).
"LP-type problems - Geometrische Optimierung zwischen Theorie und Praxis",
Karlsruhe University, Germany (Nov 7, 2003).
"Unique sink orientations of grids", Technical University Berlin,
Germany (Dec 1, 2003).
J. GIESEN
"The Flow Complex: A Data Structure for Geometric Modeling",
ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore USA
(Jan 13, 2003).
"The Flow Complex: A Geometric Data Structure and Applications",
Dagstuhl
Seminar on Computational Geometry,
Schloss Dagstuhl, Germany (Mar 19, 2003).
"Surface reconstruction based on a dynamical system",
DIMACS Workshop on Surface Reconstruction, DIMACS Center, Rutgers
University, Piscataway, New Jersey USA (Apr 30, 2003).
"Shape dimension and intrinsic metric from samples of embedded
manifolds", ECG General Workshop, FU Berlin, Germany (Jun 25, 2003)
"Alpha-Shapes and Flow Shapes are Homotopy Equivalent", 35rd
Annual ACM Symposium on the Theory of Computing (STOC), San Diego USA,
(Jun 11, 2003).
"Requirements Engineering - A Marketing Perspective", ETH Zürich, Chair
of Software Engineering group meeting (Jun 18, 2003),
"Shape segmentation and matching via flow discretization",
ECG General Workshop, FU Berlin, Germany (Jun 25, 2003).
"Induced Flows",
Combinatorics, Geometry, and Computation (CGC) Monday lecture,
Berlin Free University, Germany,
(Nov 3, 2003).
"Infering Properties from Sampled Manifolds",
INRIA Sophia Antipolis,
(Oct 3, 2003).
"Computing the Weighted Flow Complex",
Vision, Modeling, and Visualization 2003,
München TEchnical University, Germany,
(Nov 11, 2003),
M. HOFFMANN
"Pointed Encompassing Trees", Mittagsseminar, University of Eindhoven,
The Netherlands (Nov 19, 2003).
D. MITSCHE
"Spectral Techniques applied to the Hidden Cluster Problem",
3rd Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Neustrelitz, Germany
(Sep 29, 2003).
Y. OKAMOTO
"Affine Representations of Abstract Convex Geometries",
19th European Workshop on Computational Geometry,
Bonn, Germany
(Mar 25, 2003).
"Greedy edge-disjoint paths in complete graphs",
29th Workshop on Graph Theoretic Concepts in Computer Science,
Elspeet, The Netherlands
(Jun 19, 2003).
"Matroid representation of clique complexes",
9th International Computing and Combinatorics Conference (COCOON 2003),
Big Sky, MT, USA,
(Jul 26, 2003).
"Fair cost allocations under conflicts",
Algorithms Seminar,
School of Computer Science, McGill University, Montreal, Canada,
(Aug 4, 2003).
"Matroid representation of clique complexes",
18th International Symposium on Mathematical Programming (ISMP 2003),
Technical University of Denmark, Copenhagen, Denmark,
(Aug 19, 2003).
"The free complex of a two-dimensional generalized convex shelling",
2nd European Conference on Combinatorics, Graph Theory and Applications (Eurocomb'03),
Czech University of Agriculture, Prague, Czech Republic,
(Sep 9, 2003).
"Fair cost allocations under conflicts",
3rd Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Neustrelitz, Germany
(Sep 29, 2003).
"Fair cost allocations under conflicts - a game-theoretic point of view",
14th Annual International Symposium on Algorithms and
Computation (ISAAC 2003),
Kyoto, Japan.
(Dec 17, 2003).
"Recent development of abstract convex geometries",
Workshop:
Submodular Functions and Combinatorial Optimization,
Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan,
(invited talk, Dec 19, 2003).
"Edelman-Reiner's conjecture on the free complex of an
abstract convex geometry",
Ouyou Suugaku Goudou Kenkyuu Shuukai,
Ryukoku University, Ohtsu, Japan,
(Dec 20, 2003).
I. SCHURR
"Linear programming via unique sink orientations of cubes",
3rd Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Neustrelitz, Germany
(Sep 30, 2003).
"Unique sink orientations of d-cubes as a common framework for
optimization problems?",
Optimization Seminar,
IFOR, ETH Zurich (Dec 11, 2003).
B. SPECKMANN
"Allocating Vertex pi-Guards in Simple Polygons via
Pseudo-Triangulations",
Mittagsseminar, Utrecht University, The Netherlands
(Mar 11, 2003).
"Allocating Vertex pi-Guards in Simple Polygons via
Pseudo-Triangulations",
Computational Geometry Seminar,
Universitat Politècnica de Catalunya,
Barcelona, Spain
(May 30, 2003).
M. STOJAKOVIC
"Positional Games on Random Graphs",
Random Structures and Algorithms Workshop,
Poznan, Poland
(Aug 12, 2003).
"On Restricted Min-Wise Independence of Permutations",
European Conference on Combinatorics, Graph Theory and Applications,
Prague, Czech Republic
(Sep 10, 2003)
T. SZABÓ
"Extremal Problems for Transversals in Bounded Degree Graphs",
Workshop on Extremal Graph Theory, Csopak, Hungary
(Jun 23, 2003).
"Turán's Theorem in sparse random graphs",
The 11th International Conference on
Random Structures and Algorithms,
Poznan, Poland
(Aug 12, 2003).
"Turán's Theorem in sparse (pseudo)random graphs",
Combinatorics seminar,
Renyi Institute, Budapest, Hungary
(Oct 2, 2003).
"Unique Sink Orientations of Cubes",
Egerváry Seminar
Operations Research Department, Eötvös University,
Budapest, Hungary
(Oct 6, 2003).
U. WAGNER
"On the Rectilinear Crossing Number of Complete Graphs",
14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
Baltimore, MD, USA (Jan 14, 2003).
"New Constructions for Weak Epsilon-Nets",
19th
Annual ACM Symposium on Computational Geometry (SoCG),
San Diego, USA,
(Jun 9, 2003).
"Shape Dimension and Intrinsic Metric from Samples
of Manifolds with High co-Dimension",
19th
Annual ACM Symposium on Computational Geometry (SoCG),
San Diego, USA,
(Jun 10, 2003).
E. WELZL
"On the
Probability of a Random 4-gon to be Convex",
Dagstuhl
Seminar on Computational Geometry,
Schloss Dagstuhl, Germany (Mar 18, 2003).
"On Sylvester's Four Point Problem",
Meeting on Topological and Geometric Combinatorics,
Mathematisches Forschungsinstitut
Oberwolfach, Germany
(Apr 11, 2003).
"Unique Sink Orientations of Cubes and its Relations to Optimization",
DIMACS Workshop on Geometric Optimization,
Rutgers University, New Brunswick, NJ, USA
(May 19, 2003; invited lecture)
"k-Sets
and j-Facets",
Introductory Workshop on Discrete and Computational Geometry,
Mathematical Sciences Research Institute (MSRI),
(Aug 23, 2003; invited lecture, presented by Uli Wagner)
"The
Generalized Lower Bound Theorem for Polytopes
and j-Facets of Finite Point Sets",
Mathematical Sciences Research Institute (MSRI),
(Nov 17, 2003; invited lecture)
Courses and Seminars
Approximation: Theory and Algorithms (Pre-Doc Course), J. Blömer, M. Cochand, T. Erlebach, B. Gärtner, A. Steger, P. Widmayer; contact assistant: I. Schurr .
Randomized Algorithms (Pre-Doc Course), E. Welzl, B. Gärtner, U. Wagner; contact assistant: U. Wagner.
Seminar zur Algorithmischen Geometrie, B. Speckmann, E. Welzl.
Seminar der Theoretischen Informatik (Mittagsseminar), J. Giesen, B. Speckmann, T. Szabó, E. Welzl.
Colloquium in Combinatorics, Geometry, and Computation, T. Erlebach, M. Gross, H.-J. Lüthi, J. Nievergelt, B. Schiele, G. Székely, L. Van Gool, R. Wattenhofer, E. Welzl, P. Widmayer.
Theoretische Informatik (Kernfach), B. Gärtner.
Informatik II (D-MATH), J. Giesen.
Seminar Algorithmische Geometrie & Computergraphik, J. Giesen, M. Gross.
Seminar der Theoretischen Informatik (Mittagsseminar), B. Gärtner, J. Giesen, T. Szabó.
Organization of Workshops etc.
1st Gremo's Workshop on Open Problems (GWOP), Stels, Switzerland, July 8-11, 2003, (Michael Hoffmann).
Discrete and Computational Geometry, special program at the Mathematical Sciences Research Institute (MSRI), Berkeley, USA, Aug 18 - Dec 19, 2003, (Jesus A. De Loera, Herbert Edelsbrunner, Jacob E. Goodman, Janos Pach, Micha Sharir, Emo Welzl, and Günter M. Ziegler).
Mathematical Foundations of Geometric Algorithms , Workshop at Mathematical Sciences Research Institute (MSRI), Berkeley, USA, Oct 13 - 17, 2003, (Pankaj Agarwal, Herbert Edelsbrunner, Micha Sharir, and Emo Welzl).
Dissertations
Udo Adamy,
Call Admission Control and On-Line Interval Coloring
Advisors: Thomas Erlebach, D-ITET, ETH Zurich, Emo Welzl (referee)
/
Co-referee: Thomas Erlebach, D-ITET, ETH Zurich
/
Defense: Dec 11, 2003
Matthias John,
Flow complexes - Structure, Algorithms and Applications
Advisors: J. Giesen; E. Welzl (referee)
/
Co-referees: Nina
Amenta, University of California at Davis, California, USA, and
J. Giesen, ETH Zurich
/
Defense: Jun 27, 2003
Falk Tschirschnitz,
LP-Related Properties of Polytopes with Few Facets
Advisors: B. Gärtner; E. Welzl (referee)
/
Co-referees:Walter
Morris, George Mason University, Fairfax, Virginia, USA, and
B. Gärtner, ETH Zurich
/
Defense: Jun 25, 2003
Uli Wagner,
k-Sets
and Applications
Advisor: E. Welzl
/
Co-referee:
Jiri Matousek, Charles University, Prague, Czech Republic
/
Defense (at D-MATH): Jun 26, 2003
Diploma/Master Theses
Semester Theses and Pre-Doc Projects
Mattias Andersson,
Provably Good Normal Approximation Using k Nearest Neighbours
Advisor: B. Speckmann
/
31.3.2003.
Oliver Bay,
Implementation and Visualisierung eines Approximationsalgorithmus
für minimale Manhattan Netzwerke
Advisors: B. Speckmann, B. Weber
/
21.5.2003.
Lisa von Böhmer,
Analysis and Visualization of 4-Cube-Orientations
Advisor: F. Tschirschnitz
/
31.3.2003.
Lisa von Böhmer,
Hamiltonicity of Zonotopes
Advisor: Y. Okamoto
/
15.10.2003.
Matthias Hengartner,
Hamiltonian Cycles in Segment Endpoint Visibility Graphs
Advisor: M. Hoffmann
/
18.6.03.
Anja Krech,
Turan-Type Problems in the Hypercube
Advisor: T. Szabó
/
31.3.2003.
Shankar Lakshminarayanan,
P-Matrix LCP and Quadratic Programming
Advisor: B. Gärtner
/
31.3.2003.
Leonard Rüst,
LCP-Algorithmen für kleinste umschliessende Bälle
Advisor: B. Gärtner
/
15.6.2003.
Johannes Schneider,
On a Randomized Algorithm to Focus a Picture
Advisor: T. Szabó
/
4.11.2003.
Daniel Soll,
Unique Sink Orientations from Various Points of View
Advisor: B. Gärtner
/
31.3.2003.
Miscellaneous
U. ADAMY
Coordinator Mittagsseminar (since Aug 1).
Teach. Assistance Theoretische Informatik (Kernfach, SS03, contact
assistent).
K. FISCHER
Teach. Assistance Theoretische Informatik (Kernfach, SS03).
B. GÄRTNER
Teaching "Theoretical Computer Science (undergraduate)" at
Universität Konstanz, (Apr - Jul, 2003).
Program committee member of
The 11th Annual European Symposium on Algorithms (ESA 2003), Budapest, Hungary (Sep 15-20, 2003)
J. GIESEN
Coordinator ECG (Effective Computational Geomtry for
Curves and Surfaces).
Teach. Assistance Informatik I für Mathematiker und Pysiker (WS02/03).
M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial
Board.
Teach. Assistance Theoretische Informatik (Kernfach, SS03).
M. JOHN
Coordinator ECG (Effective Computational Geomtry for Curves and
Surfaces), (until April).
Teach. Assistance Logik (WS02/03).
Y. OKAMOTO
Teach. Assistance Theoretische Informatik (Kernfach, SS03).
I. SCHURR
Teach. Assistance Approximation: Theory and Algorithms (WS02/03).
Teach. Assistance Theoretische Informatik (Kernfach, SS03).
B. SPECKMANN
Program and organizing committee member of
The 15th Canadian Conference on Computational Geometry (CCCG 2003), (Halifax, Canada, Aug 11-13, 2003)
F. TSCHIRSCHNITZ
Teach. Assistance Informatik I für Mathematiker
(WS02/03; contact assistent).
Maintenance of the WWW-Site of the Graduate Program
"Combinatorics, Geometry, and Computation" and of
"Theory of Combinatorial Algorithms" group.
U. WAGNER
Coordinator Mittagsseminar (till Jul 31).
Teach. Assistance Randomized Algorithms (WS02/03).
E. WELZL
Speaker (for site Zurich) of Berlin-Zurich Graduate Program `Combinatorics,
Geometry, and Computation'.
Head of Institute of Theoretical Computer Science, ETH Zurich.
Editorial Board member of
Journal of Symbolic Computation, (B. Caviness, Ed.), Academic Press (until Aug 31, 2003)
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
Program committee member of
The 19th Ann. ACM Symp. on Computational Geometry (SoCG 2003), San Diego, USA (Jun 8-10, 2003)
Member (chair, contact person) of selection committees for
Assistenzprofessur für Systemoptimierung, Department of Information Technology and Electrical Engineering, (chair)
Professur für Theoretische Informatik, Department of Computer Science
Assistenzprofessur für Systembau, Department of Computer Science
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).
Mitglied der Evaluierungsgruppe des Fachs Mathematik in den
niedersächsischen Universitäten, Deutschland.
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.
Mitglied der Arbeitsgruppe "Tag der Lehrenden und Lernenden" der ETH Zürich.
