Current Projects

• Games and Geometric Unique Sink Orientations (SNF project 200020-112068/1)

  I am leading this two-year project, funded by the Swiss Science Foundation (SNF), and starting in 2006. Co-workers in this project are Tibor Szabo, Emo Welzl and Leo Rüst.

  Project Outline

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

• Algorithms for Complex Shapes with Certified Numerics and Topology (ACS) (STREP project No. FP6-006413-2, funded by the EU)

  I'm the site coordinator for ETH in this multinational project.

  Project Outline:

  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.

Former Projects

• Combinatorial Models for Geometric Optimization Problems (SNF project 200021-100316/1)

  I am leading this two-year project, funded by the Swiss Science Foundation (SNF), and starting in 2003. Co-workers in this project are Tibor Szabo, Emo Welzl and a PhD student to be appointed.

  Project Outline

  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 does not depend on the bit complexity of the input.

  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 matroidsoriented 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.

• ECG - Effective Computational Geometry (Shared-cost RTD (FET Open) Project No IST-2000-26473)

  This is a three-year multinational project, funded by the European Union, that started in 2001. The project deals with the efficient handling of curved objects in computational geometry. My part deals with geometric optimization problems involving curved objects, like computing the smallest enclosing ball of a set of balls, or the smallest enclosing ellipsoid of a set of points. I am working on these topics together with my PhD student Kaspar Fischer.

  The official ECG page contains more information about this project.

• Combinatorial Bounds for Geometric and Abstract Optimization Problems (SNF project 21.50617/97)

  I was leading this two-year project, funded by the Swiss Science Foundation (SNF) between 1998 and 2000. Co-workers in this project were Emo Welzl and Falk Tschirschnitz as PhD student under my supervision. Building on results obtained during this project and after its completion, Falk Taschirschnitz will finish his PhD in 2003.

  Project Outline

  The study of abstract optimization, its complexity, and its interplay with concrete (geometric) optimization problems has emerged from two lines of research that independently led to almost the same results in 1992. One line was concerned with bounds for the diameter of polytope and polyhedra graphs, the second one dealt with efficient combinatorial algorithms for Linear Programming. These are algorithms whose runtime only depends on the combinatorial structure of the linear program (like the simplex method) but not on the size of its coordinates (like the ellipsoid method).

  These independent developments share an important feature: they do not only apply to polytopes and Linear Programming but to a more general, `abstract' setting - the setting of LP-type problems. This success, made possible by taking an `abstract look' that goes beyond the concrete problem, subsequently led to many work on LP-type problems and other related frameworks.

  The proposed project aims at deepening the understanding of these frameworks and its interplay with concrete problems. Here, the abstraction is not a goal in itself but a means to understand which properties of optimization problems are crucial for an efficient treatment, and which role randomization plays in the algorithms. The idea is to treat combinatorial questions on a combinatorial level, abstracting from actual coordinates and other representation issues. The ultimate goal is to turn the insights obtained into new upper and lower bounds for the combinatorial complexity of concrete optimization problems like Linear Programming.

• GALIA - Geometric Algorithms for Industrial Applications (ESPRIT IV Long Term Research Program 28155)

  This 18 months multinational project, funded by the European Union, started in 1998. Its goal was to make computational geometry algorithms available for industrial applications. Building on the body of software already available in the CGAL library, the project added a large number of new algorithms, with particular focus on industrial strength code. As a result of the GALIA project, a company was founded that now sells software based on the CGAL library.

  My part of the project, carried out together with my PhD student Sven Schönherr dealt with geometric optimization software. The major deliverable is a quadratic programming solver tuned for applications in computational geometry, see the PhD thesis of Sven Schönherr.

• CGAL - Constructing a Geometric Algorithms Library (Esprit Project 21957)

  This 21 months multinational project which started in 1996 laid the grounds for the CGAL library, by now a standard library for computational geometry software. The goal was to show that the large body of theory available in the computational geoemtry community could actually be turned into efficient implementations. My part of the project, carried out together with my PhD student Sven Schönherr dealt with geometric optimization software.