Department of Computer Science
Theory of Combinatorial Algorithms
Prof. Emo Welzl
up print 
People
Activity Report
Previous Reports
    2012
    2011
    2010
    2009
    2008
    2007
    2006
    2005
    2004
    2003
    2002
    2001
    2000
    1999
    1998
    1997
    1996
Research
Mittagsseminar
Teaching
Workshops
Social Activities
Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2005

Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl

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


Personnel


Guests

  • Penny Haxell, University of Waterloo, Canada (Jan 11 - Feb 17)
    Ramsey Numbers for Hypergraph Cycles (Mittagsseminar, Feb 3, 2005)

  • Erik D. Demaine, Massachusetts Institute of Technology (MIT), Cambridge, USA (Jan 19 - 22)
    Origami, Polyhedra, and Linkages: Folding with Algorithms (Mittagsseminar, Jan 21, 2005)

  • Nir Halman, Technion, Haifa, Israel (Jan 24 - 26)
    On the Power of Discrete Helly Theorems and Lexicographic Helly Theorems (Mittagsseminar, Jan 24, 2005)

  • Kevin Buchin, Berlin Free University, Germany (Jan 31 - May 13)
    Incremental Construction along Space-Filling Curves (Mittagsseminar, Apr 7, 2005)

  • Maike Buchin, Berlin Free University, Germany (Jan 31 - May 13)
    Semi-Computability of the Fréchet Distance between Surfaces (Mittagsseminar, Apr 12, 2005)

  • Dan Hefetz, Tel Aviv Univiversity, Tel Aviv, Israel, (Apr 17-22)
    Avoider-Enforcer Games, (Mittagsseminar, Apr 19, 2005)

  • Uli Wagner, Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Israel (Apr 16-24)
    k-Sets and Topological Invariants of Plane Curves (Mittagsseminar, Apr 22, 2005)

  • Uwe Schöning, Ulm University, Ulm, Germany (Apr 21)
    Algorithmics in Exponential Time, (Seminar SAT, Apr 21, 2005)
    Quest for the Fastest SAT Algorithm, (Mittagsseminar, Apr 21, 2005)

  • Gyula Károlyi, Eötvös University, Budapest, Hungary (May)
    Structure Theorems for Set Addition: the Power of the Combinatorial Nullstellensatz (Workshop on Geometric Combinatorics and Optimization, May 24, 2005)
    Set Addition in Noncommutative Groups, (Mittagsseminar, May 26, 2005)

  • Shakhar Smorodinsky, Courant Institute for Mathematical Sciences, New York University, USA (May 5-8)
    On the Chromatic Number of Some Geometric Hypergraphs, (Mittagsseminar, May 6, 2005)

  • János Barát, TU Lyngby, Denmark (May 8-13)
    The Slope Parameter of Graphs (Mittagsseminar, May 10, 2005)

  • Takeaki Uno, National Institute of Informatics, Tokyo, Japan (since May 9)
    Tree Enumeration Algorithms (Mittagsseminar, Jul 26, 2005)
    Enumerating Dense Subgraphs (Mittagsseminar, Dec 1, 2005)

  • Michael Joswig, Technische Universität Darmstadt, Germany (May 9)
    Polytope Propagation (Optimisation Seminar, May 9, 2005)

  • Jiří Matoušek, Charles University, Prague, Czech Republic (May 15 - July 8)
    Voronoi Diagrams with Neutral Zones (Workshop on Geometric Combinatorics and Optimization, May 24, 2005)
    New Badly Embeddable Spaces (presenting work of Subhash Khot and Assaf Naor) (Mittagsseminar, Jun 23, 2005)

  • András Recski, Budapest University of Technology and Economics (May 23-24)
    Some Applications of Combinatorial Optimization in Statics (Mittagsseminar, May 24, 2005)

  • Takashi Horiyama, School of Informatics and Mathematical Science, Kyoto University, Japan (Jun 9-10)

  • Edgar Ramos, University of Illinois at Urbana-Champaign, USA (Jun 11-18)
    Manifold Reconstruction from Point Samples (Mittagsseminar, Jun 15, 2005)

  • Ron Aharoni, Technion - Israel Institute of Technology, Haifa, Israel (Jun 12-19)
    The Erdös-Menger Conjecture (Mittagsseminar, Jun 14, 2005)

  • Pankaj K. Agarwal, Duke University, Durham, USA (Jun 13-16)
    Optimal Coresets for Approximating the Extent of Shallow Levels (Mittagsseminar, Jun 15, 2005)

  • Csaba D. Tóth, Massachusetts Institute of Technology, Cambridge, USA (Jun 18-22)
    A Vertex-Face Assignment for Plane Graphs (Mittagsseminar, Jun 21, 2005)

  • Avi Wigderson, Institute for Advanced Study, Princeton, USA (Jun 27)
    Zigzag Products, Expander Constructions, Connections and Applications (Colloquium Department of Computer Science, Jun 27, 2005)

  • Bettina Speckmann, TU Eindhoven, The Netherlands (Jul 2-6)
    On Rectangular Cartograms (Mittagsseminar, Jul 6, 2005)

  • Yoshio Okamoto, Toyohashi University of Technology, Japan (Jul 3-6)
    All-Pairs Shortest Paths with Real Weights in O(n^3 /log n) Time (Mittagsseminar, Jul 7, 2005)

  • Maike Buchin, Berlin Free University, Germany (Jul 3-9)
    Minimizing the Total Absolute Gaussian Curvature in a Terrain is Hard (Mittagsseminar, Jul 7, 2005)

  • Kevin Buchin, Berlin Free University, Germany (Jul 3-9)
    The Flow Complex: General Structure and Algorithm (Mittagsseminar, Jul 7, 2005)

  • Hans-Martin Will, Rosetta Inpharmatics Inc., Seattle, USA (Jul 3-9)
    Challenges and Opportunities in the Post-Genome Era - An Introduction to Functional Genomics and Proteomics (Mittagsseminar, Jul 19, 2005)

  • Masashi Kiyomi, National Institute of Informatics (NII), Japan (Jun 28 - Jul 28)
    Efficient Algorithms for the Electric Power Transaction Problem (Mittagsseminar, Jul 21, 2005)

  • Berit Johannes (since Aug 1)
    Earliest Start Time Scheduling in AND/OR-graphs - An Introduction (Mittagsseminar, Oct 18, 2005)

  • Andreas S. Schulz, Massachusetts Institute of Technology, Cambridge, MA (since Aug 1)
    Single-Machine Scheduling with Precedence Constraints (Optimization and Applications Seminar, Nov 14, 2005)
    How many diamonds can be packed in a Chinese checkerboard? (Mittagsseminar, Dec 6, 2005)
    Games in Networks, and the Price of Anarchy (Informatik Kolloquium, Dec 19, 2005)

  • Mutsunori Yagiura, Kyoto University, Japan (Aug 16-22)
    Exact Algorithms for Two-Dimensional Strip Packing Problems (Mittagsseminar, Aug 18, 2005)

  • Karl Lieberherr, Northeastern University, Boston (Aug 23)
    Algorithmic Problems Related to the Tyranny of the Dominant Decomposition (Mittagsseminar, Aug 23, 2005)

  • Michael Krivelevich, Tel Aviv University, Tel Aviv, Israel (Sep 17-24)
    Property Testing in Graphs of General Density (Mittagsseminar, Sep 21, 2005)

  • József Beck, Rutgers University, New Brunswick, USA (Sep 22-25)
    Every Finite Point Set in the Plane is a Weak Winner! (Mittagsseminar, Sep 22, 2005)

  • Ken Satoh, National Institute of Informatics, Japan (Oct 6-11)
    Enumerating Minimally Revised Specifications using Dualization (Mittagsseminar, Oct 11, 2005)

  • Mitsuo Motoki, Japan Advanced Institute for Science and Technology, Japan (Oct 7-8)
    Test Instance Generation for MAX 2SAT (Mittagsseminar, Oct 7, 2005)

  • Micha Sharir, Tel Aviv University, Tel Aviv, Israel (Oct 6-26)
    On the ICP Algorithm (Mittagsseminar, Oct 12, 2005)

  • Uli Wagner, Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Israel (Oct 23-28)

  • Ryuhei Uehara, Japan Advanced Institute of Science and Technology, Japan (Oct 24 - Nov 23)
    Efficient Algorithms for the Longest Path Problem (Mittagsseminar, Oct 25, 2005)

  • Ulrike von Luxburg, Fraunhofer IPSI, Darmstadt, Germany (Nov 3-4)
    Convergence of Random Graph Laplacians (Mittagsseminar, Nov 3, 2005)

  • Volker Kaibel, Zuse-Institut Berlin, Germany (Dec 5-7)
    Breaking Symmetries by Orbitopes (Optimisation Seminar, Dec 5, 2005)

  • Rahul Savani, London School of Economics, London, UK (Dec 12-16)
    Hard-to-Solve Bimatrix Games (Mittagsseminar, Dec 13, 2005)

  • Bernhard von Stengel, London School of Economics, London, UK (Dec 12-16)
    Strategic Characterization of the Index of an Equilibrium (Mittagsseminar, Dec 15, 2005)


Grants

  • Transversals and Colorings of Graphs

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

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

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

  • Non-linear Manifold Learning

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

  • Combinatorial Models for Geometric Optimization Problems

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

  • Computational Geometry Aspects of Gamut Mapping

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

    I. Classifications of Oriented Matroids (Combinatorics)
    II. State Polytopes of Polynomial Ideals (Algebra)
    III. Minkowski Addition of Polytopes and Convex Hull (Geometric Computation)
    IV. 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, and R. Thomas, University of Washington)


Publications

  • Books

    J. E. Goodman, J. Pach, E. Welzl (Eds.), Combinatorial and Computational Geometry, Mathematical Sciences Research Institute Publications, Cambridge University Press (2005).

  • Journals (with refereeing)

    N. Alon, M. Krivelevich, J. Spencer, T. Szabó, Discrepancy games, Electronic Journal of Combinatorics 12 (2005) R51.

    I. Bárány, K. Fukuda, A case when the union of polytopes is convex, Linear Algebra and its Applications 397 (2005) 381 - 388.

    P. Csorba, On the biased n-in-a-row game, Discrete Mathematics, 305:1-3 (2005) 100-111.

    S. Felsner, B. Gärtner, F. Tschirschnitz, Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines, Discrete & Computational Geometry 34 (2005) 411-437.

    A. Frieze, M. Krivelevich, O. Pikhurko, T. Szabó, The game of JumbleG, Combinatorics, Probability and Computing 14 (2005) 783-793.

    M. Hoffmann, A simple linear algorithm for rectilinear 3-centers, Computational Geometry - Theory and Applications 31:3 (2005) 150-165.

    K. Kashiwabara, M. Nakamura, Y. Okamoto, The affine representation theorem for abstract convex geometries, Computational Geometry - Theory and Applications 30 (2005) 129-144.

    B. Speckmann, Cs. D. Tóth, Allocating vertex pi-guards in simple polygons via pseudo-triangulations, Discrete & Computational Geometry 33 (2005) 345-364.

    M. Stojakovic, T. Szabó, Positional games on random graphs, Random Structures & Algorithms 26 (2005) 204-223.

    B. Sudakov, T. Szabó, V. Vu, A generalization of Turán's Theorem, Journal of Graph Theory 49:3 (2005) 187-195.

    T. Szabó, V. Vu, Exact k-wise intersection theorems, Graphs and Combinatorics 21:2 (2005) 247-261.

  • Conference Proceedings (with selection process)

    U. Adamy, Th. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, E. Welzl, Off-line admission control for advance reservations in star networks, Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA`04), Lecture Notes in Computer Science 3351 (2005) 211-224.

    B. Aronov, S. Smorodinsky, On geometric permutations induced by lines transversal through a fixed point, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) 251-256.

    Z. Beerliova, F. Eberhard, Th. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, L. Shankar Ram, Network discovery and verification, Proc. Graph Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 3787 (2005) 127-138.

    R. Berke, T. Szabó, Relaxed coloring of cubic graphs, European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB) (2005) 341-344.

    M. Bläser, L. Shankar Ram, An improved approximation for TSP with distances one and two, Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science 3623 (2005) 504-515.

    M. Bläser, L. Shankar Ram, Approximate fair cost allocation in metric TSP games, Proc. 3rd Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science 3879 (2005) 82-95.

    M. Bläser, L. Shankar Ram, M. Sviridenko, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, Proc. Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 3608 (2005) 350-359.

    F. Cazals, J. Giesen, M. Pauly, A. Zomorodian, Conformal alpha shapes, Proc. 2nd Symposium on Point Based Graphics (SPBG) (2005) 55-61.

    T.K. Dey, J. Giesen, S. Goswami, Delaunay triangulation approximates anchor hull, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) 1028-1037.

    T.K. Dey, J. Giesen, E. Ramos, B. Sadri, Critical points of the distance to an epsilon-sampling on a surface and flow complex reconstruction, Proc. 21st Annual ACM Symposium on Computational Geometry (SOCG) (2005) 218-227.

    A. Fiat, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl, Online conflict-free coloring for intervals, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) 545-554.

    B. Gärtner, W. D. Morris Jr., L. Rüst, Unique sink orientations of grids, Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science 3509 (2005) 210-224.

    B. Gärtner, L. Rüst, Simple stochastic games and P-matrix generalized linear complementarity problems, Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science 3623 (2005) 209-220.

    J. Giesen, D. Mitsche, Boosting spectral partitioning by sampling and iteration, Proc. 16th Annual International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 3827 (2005) 473-482.

    J. Giesen, D. Mitsche, Bounding the misclassification error in spectral partitioning in the planted partition model, Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 3787 (2005) 409-420.

    J. Giesen, D. Mitsche, Reconstructing many partitions using spectral techniques , Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science 3623 (2005) 433-444.

    J. Giesen, E. Schuberth, K. Simon, P. Zolliker, Toward interactive image-dependent gamut mapping: Fast and accurate gamut boundary determination, Proc. IS&T/SPIE Symposium on Electronic Imaging (2005) 201-210.

    M. Hoffmann, Cs. D. Toth, Pointed and colored binary encompassing trees, Proc. 21st Annual ACM Symposium on Computational Geometry (SOCG) (2005) 81-90.

    F. Kuhn, P. von Rickenbach, R. Wattenhofer, E. Welzl, A. Zollinger, Interference in cellular networks: The minimum membership set cover problem, Proc. 11th Annual International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science 3595 (2005) 188-198.

    M. Marciniszyn, D. Mitsche, M. Stojakovic, Balanced avoidance games on random graphs, Proc. European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB); Discrete Mathematics & Theoretical Computer Science (2005) 329-334.

    M. Pauly, N. Mitra, J. Giesen, L. Guibas, M. Gross, Example-based 3D scan completion, Proc. 3rd Symposium on Geometry Processing (SGP) (2005) 23-32.

    T Szabó, I. Schurr, Jumping doesn't help in abstract cubes, Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO) (2005) 225-235.

  • Other (including submitted work)

    K. Buchin, J. Giesen, Flow complex: General structure and algorithm, Proc. 17th Canadian Conference on Computational Geometry (CCCG) (2005) 270-273.

    M. Buchin, J. Giesen, Minimizing the total absolute Gaussian curvature in a terrain is hard, Proc. 17th Canadian Conference on Computational Geometry (CCCG) (2005) 192-195.

    M. Henk, J. Matousek, E. Welzl (Eds.), Discrete Geometry, Report No. 17/2005, Oberwolfach Reports 2:2 (2005) 925-994.

    M. Hoffmann, Cs. D. Tóth, Pointed binary encompassing trees: Simple and optimal, Abstracts 21st European Workshop on Computational Geometry (EuroCG) (2005) 93-96.


Lectures

Courses and Seminars

Winter 04/05

Summer 05

Organization of Workshops etc.


Dissertations


Diploma/Master Theses

  • Danilo Negro, Algorithms for the Minimum Path Cover Problem in Graphs
    Advisor: Y. Okamoto / 1.3.2005
  • Andreas Razen, Counting Satisfying 2-SAT Assignments
    Advisors: T. Szabó, E. Welzl / 28.2.2005
  • Marion Wenger, Hall Type Theorems for Graphs and Hypergraphs - an Approach Through Triangulations
    Advisors: T. Szabó, P. Csorba / 28.2.2005
  • Philipp Zumstein, Comparison of Spectral Methods Through the Adjacency Matrix and the Laplacian of a Graph
    Advisor: T. Szabó / 28.2.2005

Semester Theses

  • Miklos Balint, Surface Reconstruction and Medial Axis from Flow Complex
    Advisor: J. Giesen / 29.09.2005
  • Yves Brise, Hierachical Spectral Clustering
    Advisors: J. Giesen, D. Mitsche / 26.9.2005
  • Heidi Gebauer, On Counting the Number of Forests in a Graph
    Advisor: Y. Okamoto / 22.3.2005
  • Claudia Käppeli, Satisfiability in 2-Satisfiable Formulae
    Advisor: E. Welzl / 23.10.2005
  • Joest Smit, Optimization over Conic Regions
    Advisor: B. Gärtner / 21.10.2005

Miscellaneous

R. BERKE
Teach. Assistance Erfüllbarkeit logischer Formeln - Kombinatorik und Algorithmen (WS04/05).
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Teach. Assistance Seminar SAT (SS05).
Teach. Assistance Coordinator.
Attended the conferences/courses/workshops:
Doccourse Prague, Modern Methods in Ramsey Theory, Prague, Czech Republic (Jan 22 - Feb 26, 2005).
3rd European Conference on Combinatorics, Graph Theory and Applications (Eurocomb), Berlin, Germany (Sep 5-9, 2005).
5th Annual Workshop on Combinatorics, Geometry, and Computation (CGC) , Hiddensee, Germany (Sep 25-28, 2005).

P. CSORBA
Teach. Assistance Topological Combinatorics (WS04/05).
Attended the conferences/courses/workshops:
Workshop on Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach, Germany (Apr 10-16, 2005)
Algebraic and Geometric Combinatorics, Anogia, Crete (Aug 20-26, 2005).

B. GÄRTNER
Member of the CGAL Editorial Board.
Coordinator ACS.

J. GIESEN
Program committee member of

  • Symposium on Point-Based Graphics, Stony Brook, USA (2005)

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

D. MITSCHE
Teach. Assistance Informatik I (D-ITET) (WS04/05).
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Coordinator Mittagsseminar.
Attended the conferences/courses/workshops:
31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Metz, France (Jun 23-25, 2005).
15th International Symposium on Fundamentals of Computation Theory (FCT), Lübeck, Germany (Aug 17-20, 2005).
3rd European Conference on Combinatorics, Graph Theory and Applications (EuroComb`05), Berlin, Germany (Sep 5-9, 2005).
16th International Symposium on Algorithms and Computation (ISAAC), Hainan, China (Dec 19-21, 2005).

Y. OKAMOTO
Teach. Assistance External Memory Algorithms and Data Structures (WS04/05).

A. RAZEN
Teach. Assistance Approximate Methods in Geometry (SS05).
Attended the conferences/courses/workshops:
5th Annual Workshop on Combinatorics, Geometry, and Computation (CGC), Hiddensee, Germany (Sep 25-28, 2005).

L. RÜST
Teach. Assistance Informatik I (D-MATH, D-PHYS) (WS04/05).
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Webmaster www-gremo.
Attended the conferences/courses/workshops:
11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Technische Universität Berlin, Germany (Jun 8-10, 2005).
15th International Symposium on Fundamentals of Computation Theory (FCT), Lübeck, Germany (Aug 17-20, 2005).

E. SCHUBERTH
Teach. Assistance Bild-Farbe-Reproduktion (WS04/05).
Teach. Assistance Computational Marketing (SS05).
Attended the conferences/courses/workshops:
IS&T/SPIE 17th Annual Symposium on Electronic Imaging, San Jose, USA (Jan 18, 2005).
Upper Rhine Algorithms Workshop (URAW), Tübingen, Germany (Jul 18, 2005).

M. STOJAKOVIC
Teach. Assistance Graph Theory (WS04/05).
Teach. Assistance Extremal Combinatorics (SS05).
Attended the conferences/courses/workshops:
Workshop Erdös Magic for Algorithms and Games, Bertinoro, Italy (Apr 24-29, 2005).
The 12th International Conference on Random Structures and Algorithms, Poznan, Poland (Aug 1-5, 2005).
3rd European Conference on Combinatorics, Graph Theory and Applications (Eurocomb), Berlin, Germany (Sep 5-9, 2005).

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.
Vice-Chair, Department of Computer Science, ETH Zurich.

Program committee member of

Editor (with Jacob Eli Goodman and János Pach) of Combinatorial and Computational Geometry (Mathematical Sciences Research Institute Publications), Cambridge University Press.

Editorial Board member of

Member (chair, contact person) of selection committees for

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

Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
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.

Coreferee for habilitation of

  • Benjamin Doerr, IntegralApproximation (Kiel University, Germany)

F. WESSENDORP
Implementation and documentation of a convex quadratic programming solver.

P. ZUMSTEIN
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Attended the conferences/courses/workshops:
5th Annual Workshop on Combinatorics, Geometry, and Computation (CGC), Hiddensee, Germany (Sep 25-28, 2005).


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