Externally funded projects

• Stable Medial Axis under Motion

  (Funded by the Swiss National Science Foundation, joint project with Mark Pauly). The medial axis is one of the fundamental geometric concepts in computational geometry, 3D shape modeling, and image processing. Introduced by Blum as a tool for image analysis, the medial axis has since then been used in many different contexts, e.g., shape recognition, motion planing and reverse engineering.
  Our interest in the medial axis is twofold. First, the medial axis is a very interesting mathematical object in itself that poses many computational and mathematical challenges. Second, the medial axis conceptually appears in many geometric modeling applications. In most of these applications a shape is given to us only in form of a finite sample, e.g., a laser range scan of a 3D solid, or a set of positions of the atoms of a molecule measured by x-ray crystallography. The use of the medial axis for such data has been mostly restricted to theoretical analysis. Few applications have been presented that explicitly compute the medial axis for geometric processing tasks on acquired sample sets. One of the main reasons for its limited practical use is the notorious instability of the medial axis transform.
  Our goal is to give a new definition of an approximate medial axis that is stable under a set of meaningful perturbations and at the same time respects the intrinsic scales of the data. This would allow scalable geometric processing operations based on the medial axis for non-uniformly sampled data, thus greatly enhancing the set of potential input data. Additionally, we want to derive algorithms for maintaining the medial axis for kinetic data sets, i.e., shapes that move or deform over time. Motion is fundamental in many disciplines that model the physical world, such as robotics, computer graphics, computational biology, or physics. A kinetic medial axis is of great interest in such fields, as it is directly linked to the concept of an interface between two or more different shapes. An interface can be defined as the subset of the medial axis of the dual shape that contains all points with nearest neighbors in more than one shape. Interfaces play an important role in machine learning as decision boundaries, in fluid dynamics simulations as boundary between different fluids, and in molecular dynamics simulations as inter-molecular or contact surfaces between different macromolecules.

• Revisiting the Flexibility of Proteins

  (Funded by INRIA). Understanding the way proteins adopt their 3D structure, the folding problem, or the way macro-molecular complexes get formed, the docking problem, are two of the most challenging problems in structural biology. Since proteins in vivo vibrate at various frequencies addressing the aforementioned problems requires modeling protein flexibility. In this project we plan to develop new approaches towards modeling protein flexibility based on geometric and topological tools.
  Participating researchers: Frédéric Cazals (INRIA Sophia Antipolis, project leader), Michael Nilges (Institut Pasteur) and Joachim Giesen

• Algorithms for Robust Conjoint Analysis

  (Funded 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 on the complexity.

• Computational Geometry Aspects of Gamut Mapping

  (Funded 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.

• Algorithms for Complex Shapes with certified numerics and topology

  (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.
  I wrote the part on shape learning in the proposal for this project.
  

• Non-linear Manifold Learning (completed)

  (Funded 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 by other proximity data structures.

• Effective Computational Geometry for Curves and Surfaces (completed)

  (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 Voronoi 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.
  Within the project I focused on surface reconstruction and coordinated the project locally in Zurich (since May 2003).