Wednesday March 31st 
Thursday April 1st 
Friday April 2nd 

9h30  9h45  Welcome  P. Giblin
Skeletons of curves and surfaces 
K. Polthier
Prescribed Mean Curvature Flow for Mesh Optimization 
9h45  10h  
10h  10h15  Introduction  
10h15  10h30  D. Halperin
Arrangements 

10h30  10h45  
10h45  11h  Coffee break  Coffee break  
11h  11h15  Coffee break  
11h15  11h30  A. Lieutier  G. Vegter
Meshing of surfaces 

11h30  11h45  E. Fogel  
11h45  12h  JD. Boissonnat
Voronoi diagrams 

12h  12h15  R. Wein  N. Kruithof  
12h15  12h30  
12h30  14h30  Lunch break  Lunch break  Lunch break 
14h30  14h45  B. Schölkopf
Learning with kernels 
T. Dey
Sample Based Modeling 
E. Berberich 
14h45  15h  
15h  15h15  S. Petitjean  
15h15  15h30  
15h30  15h45  Coffee break  
15h45  16h  Coffee break  Coffee break  
16h  16h15  M. Teillaud  
16h15  16h30  K. Mehlhorn
Algebra and Robustness issues 
J. Giesen
Surface reconstruction 

16h30  16h45  M. Karavelas  
16h45  17h  
17h  17h15  Break  S. Oudot  
17h15  17h30  B. Mourrain  
17h30  17h45  Break  
17h45  18h  I. Emiris  S. Plantiga  
18h  18h15  
18h15  18h30  M. Pouget  
18h30  18h45  
18h45  
20h00  Workshop dinner 
Invited talks
Bernhard Schölkopf
MPI für biologische Kybernetik Tübingen 
Learning with kernels
The talk will start with a short introduction to kernel methods in machine learning. Following this, we will describe how some recent methods for nonlinear dimensionality reduction (such as locally linear embedding, or the graph Laplacian algorithm) can be viewed as kernel methods. 
Peter Giblin
The University of Liverpool 
Recent work on skeletons of curves and surfaces
The skeleton or medial axis of a curve in the plane or a surface in 3space has been an object of interest ever since Blum introduced the idea in the context of biological shape in the 1970s. It is used as in some sense an index of the shape of the curve or surface and contains a great deal of information about the shape. In this talk I shall review some recent work, including construction of the skeleton using computer graphics, the evolution of the skeleton in 3D through a family of surfaces, the existence of geometrical constraints on the skeleton at points where it is singular, and the remarkable work of Damon which seeks to reduce the 3D skeleton to 'essentially' a tree structure. 
Tamal Dey
The Ohio State University 
Delaunay and Voronoi Diagrams in Sample Based Modeling
Modeling geometry from point samples offers flexibility in many science and engineering applications. Delaunay and Voronoi diagrams of the input points provide a data structure from which several geometric and topological properties of the sampled object can be derived. In this talk we present algorithms and their implementations for sampling, reconstructing, segmenting and extracting features from the Delaunay/Voronoi diagrams of the point sample of a shape. 
Konrad Polthier
Zuse Institute Berlin 
Prescribed Mean Curvature Flow for Mesh Optimization
We introduce anisotropic curvature operators for polyhedral surfaces and present applications in the context of noise removal and geometric feature detection. The discrete differential operators combine techniques from discrete geometry, finite element numerics and computer graphics. 
ECG overview talks
These talks will present the achievements of the ECG consortium in the different work areas.
Dan Halperin
Tel Aviv University  Israel 
Arrangements 
Kurt Mehlhorn
MPI Saarbrücken  Germany 
Algebraic and Arithmetic issues 
JeanDaniel Boissonnat
INRIA Sophia Antipolis  France 
Voronoi diagrams I and II 
Joachim Giesen
ETH Zürich  Switzerland 
Surface reconstruction 
Gert Vegter
Rijksuniversiteit Groningen  Netherlands 
Meshing of surfaces 
Short talks
(sorted by alphabetical order of speakers)
Eric Berberich
MPI Saarbrücken  Germany. 
Recent Progress on Computing Arrangements of Quadrics
A cell in an arrangement of quadrics can be computed using a
projection of the spatial intersection curves to the plane. We present
an exact, robust and efficient C++ implementation that computes the
arrangements induced by the intersection curves on the lower and upper
part of each quadric in such an arrangement.
Joint work with Elmar Schömer and Nicola Wolpert 
Ioannis Z. Emiris,
National Kapodistrian University of Athens, Greece. 
Computing with real algebraic numbers of degree less than 5
Our motivation is the efficient and exact implementation of predicates in computeraided design and nonlinear computational geometry, eg. in computing arrangements of conic arcs. We compare real algebraic numbers by precomputing generalized Sturm sequences, thus avoiding iterative algorithms. One important ingredient, of independent interest, is the determination of rational isolating points as functions of the coefficients, between any pair of real roots. We also exploit invariants and common subexpressions, in order to minimize the practical complexity. The degree of the tested quantities in the input coefficients is optimal for algebraic numbers of degree up to 3, and for degree 4 in most cases. All degeneracies are handled, including when the polynomials drop degree. The method applies to real solving of pairs of quadratic equations, and to sign determination of polynomials over algebraic numbers of degree less than 5. These operations have been implemented for numbers of degree up to 4, in a recent module of library Synaps 2.1. We have compared against certain general algebraic packages which, unlike our code, are able to treat arbitrarydegree algebraic numbers. First, against the publicly available approach by R. Rioboo (Issac'92) implemented on Axiom, the implementation by Guibas, Karavelas, and Russel [GKR04], and the builtin capabilities of Core 1.6, Maple 9, and Synaps 2. Our code runs about 4 times faster than the filtered version of [GKR04] ; the other implementations are slower. Second, the code was used by Athanasios Kakargias with the curved kernel (see PionTeillaud's talk) for circles and CGAL arrangements, where it was never slower and usually more than 3 times faster than the Leda 4.2 library. This is joint work with Elias Tsigaridas, National Kapodistrian University of Athens, Greece. 
Efi Fogel
Tel Aviv University  Israel. 
CGAL Arrangements of Curves: More Generic than Ever 
Menelaos Karavelas
University of Notre Dame, USA. 
A computational framework for handling motion
We present a framework for implementing geometric algorithms involving motion. It is written in C++ and modeled after and makes extensive use of CGAL (Computational Geometry Algorithms Library). The framework allows easy implementation of kinetic data structure style geometric algorithmsones in which the combinatorial structure changes only at discrete times corresponding to roots of functions of the motions of the primitives. This paper discusses the architecture of the framework and how to use it. We also briefly present a polynomial package we wrote, that supports exact and filtered comparisons of real roots of polynomials and is extensively used in the framework. We plan to include our framework in the next release of CGAL. This joint work with Leonidas Guibas and Daniel Russell from Stanford University. 
Nico Kruithof
Rijksuniversiteit Groningen  Netherlands. 
Meshing of skin surfaces
Skin surfaces are traditionally used for the visualisation of molecules. They form a class of tangent continuous surfaces defined in terms of a set of balls (the atoms of the molecule) and a shrink factor. More recently, we used skin surfaces for approximation purposes. We have developed an algorithm to approximate a skin surface with a topological correct mesh. The algorithm consists of two steps: first construct a coarse topologically correct mesh and then a refinement step. The complexity of the coarse mesh is quadratic in the number of input balls, which is worst case optimal. In the talk, I present the main ideas of our algorithm and describe the use of CGAL in our implementation. 
André Lieutier Dassault Systèmes Provence  Properties of the distance
fonctions and Medial Axis of non smooth objects
A natural extension of the gradient of the distance function to a finite point sample defines a flow which, together with its associated critical points and stable/unstable manifolds have been proven to provide powerfull tools for understanding which topological feature can be captured by a sampling of an object, at least for smooth (positive lfs) objects. After a brief presentation of theses notions, we examine how these properties extends to the distance function to an arbitary compact set, including a non smooth boundary. As an application we examine the computation of the "LambdaMedial Axis", a subset of the Medial Axis which remains stable under Hausdorff distance perturbations of the boundary. On can then derive a very simple algorithm for the computation of the "LambdaMedial Axis" which is an illustration of a model of computation taking aproximate inputs. Joint work with Frédéric Chazal, Université de Bourgogne, Dijon, France. 
Bernard Mourrain
INRIA Sophia Antipolis, France. 
Algorithms for curves and surfaces; an algebraic point of view
The treatment of shapes on a computer leads to a large domain of investigation, connected to topological, differential, numeric, symbolic questions and with many applications. In this talk, we will consider representation of shapes based on algebraic models, in particular on parameterised and implicit representation. We will describe different techniques to compute points of intersection on curves and surfaces, which involve approximate, control or certified computation. A special attention will be given to topology certification. We will mentioned 3 types of methods for computing the topology of a planar or a three dimensional curve or for meshing an implicit surface even in the presence of singularity. These methods will be illustrated by experiments with the library axel, dedicated to algebraic curves and surfaces. Joint work with J.P. Técourt, G. Gatellier, J.P. Pavone, G Comtes. 
Steve Oudot
INRIA Sophia Antipolis, France. 
An Effective Condition for Sampling Surfaces with Guarantees
The notion of esample, as introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces. Of particular interest is the fact that, if E is an esample of a smooth surface S for a sufficiently small e, then the Delaunay triangulation of E restricted to S, DelS(E), is a good approximation of S, both in a topological and in a geometric sense. Hence, if one can construct an esample, one also gets a good approximation of the surface. Moreover, correct reconstruction is ensured by various algorithms. In this talk, we will introduce the notion of loose esample. We show that the set of loose esamples contains and is asymptotically identical to the set of esamples. The main advantage of loose esamples over esamples is that they are easier to check and to construct. Work in collaboration with JeanDaniel Boissonnat. 
Sylvain Petitjean
INRIA Lorraine, France. 
Intersecting Quadrics: An Efficient and Exact Implementation
We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the nearoptimal algorithm recently introduced by Dupont et al. (see SoCG'03). Unlike existing implementations, it correctly identifies and parameterizes all the connected components of the intersection in all the possible cases, returning parameterizations with rational functions whenever such parameterizations exist. In addition, the coefficient field of the parameterizations is either minimal or involves one possibly unneeded square root. Joint work with S. Lazard and L. M. Peñaranda, INRIA Lorraine. 
Simon Plantinga
University of Groningen, The Netherlands. 
Isotopic approximation of implicit curves and surfaces
Several algorithms exist for generating piecewise linear approximations of implicit surfaces, but most of them are based on a userdefined stepsize or bounds to indicate the precision, and therefore cannot guarantee topological correctness. Interval arithmetic provides a mechanism to determine global properties of the implicit function. In this talk we present an algorithm that uses these properties to generate a piecewise linear approximation of implicit curves and surfaces, that is isotopic to the curve or surface itself. The algorithm is simple and fast, and is among the first to guarantee isotopy for implicit surface meshing. 
Marc Pouget
INRIA Sophia Antipolis, France. 
Differential geometry of sampled smooth surfaces: principal frames, umbilics and ridges
In this talk we investigate properties of curvature related quantities and objects on a sampled smooth surface given as a triangulated surface or a point cloud. First, we present an algorithm which consists of fitting the local representation of the surface as a height function, and derive the corresponding approximation order for the estimation of pointwise differential quantities. Second, we show how these differential quantities up to the fourth order can be used to detect and the classify umbilics and report ridge lines extrema of principal curvatures. Joint work with Frédéric Cazals, INRIA Sophia Antipolis. 
Monique Teillaud
INRIA Sophia Antipolis, France. 
Towards a CGAL curved kernel
The kernel of the CGAL library provides several functionalities which are, however, mostly restricted to linear objects. We present the design, implementation and testing of a kernel for computing arrangements of circular arcs. A preliminary implementation exists also for conic curves. We plan to submit this curved kernel framework as a new CGAL package. Joint work with Sylvain Pion, INRIA Sophia Antipolis, Ioannis Z. Emiris, Athanasios V. Kakargias and Elias P. Tsigaridas, National Kapodistrian University of Athens, Greece. 
Ron Wein
TelAviv University, Israel. 
Continuous Path Verification in MultiAxis NCMachining
We introduce a new approach to the problem of collision detection between a rotating millingcutter of an NCmachine and a model of a solid workpiece, as the rotating cutter continuously moves near the workpiece. Having five degrees of motion freedom, this problem is hard to solve exactly and we approximate the motion of the tool by a sequence of subpaths of pure translations interleaved with pure rotations. The detection problem along each subpath is then solved by using radial projection of the obstacles (the workpiece and other parts of the NCmachine) around the tool axis to obtain a collection of critical surface patches in space, and by examining planar silhouettes of these surface patches. We thus reduce the problem to successive computations of the lower envelope of a set of planar curves of degree 2  this reduction is exact, and incurs no loss of accuracy. We have implemented our algorithm in the {\sc Irit} environment for solid modeling, using an extension package of the {\sc Cgal} library for computing envelopes. The algorithm, combined with the proper data structures, solves the collision detection problem in a robust manner, yet it yields efficient computation times as our experiments show. Our approach yields accurate results in case of a purely translational motion, and provides guaranteed (and good) approximation bounds in case the motion includes rotations. Joint work with Dan Halperin, TelAviv University, and with Oleg Ilushin and Gershon Elber, Technion, Haifa, Israel. 