Un projet du programme "Jeunes chercheuses et jeunes chercheurs" de l'
Presentation
L’évolution rapide des systèmes de mesure, des ordinateurs et des systèmes d’affichage entraîne une révolution. Ces changements technologiques, et notamment les nouvelles capacités de calcul, permettent la modélisation, la simulation et la visualisation de formes complexes. L’ingénierie numérique, qui substitue ainsi la maquette numérique au prototype physique, puis le calcul à l’expérience, permet à l’ingénieur “d’essayer le réel”, c’est-à-dire de concevoir, de prévoir et d’anticiper à moindre coût. Pourtant, et même si l’on est forcé de constater les bénéfices apportés par la puissance de calcul, l’ingénierie numérique se confronte aujourd’hui aux limitations de la réalité machine (les représentations sont discrètes, la mémoire est limitée et les calculs approchés). De telles limitations entraînent des problèmes de robustesse et de fiabilité qui se traduisent d’une part en une grande difficulté à certifier les algorithmes, et d’autre part en un temps considérable passé à régler des heuristiques ou à mettre au point des correctifs incertains.
Les difficultés à certifier les algorithmes proviennent essentiellement d’une séparation trop marquée entre les mathématiques et l’informatique. Nous avons d’un côté une description mathématique (idéalisée) des formes avec des algorithmes performants en théorie. De l’autre une réalité machine avec ses limitations et une absence de certification provenant de l’utilisation essentielle d’heuristiques.
L’objectif de ce projet consiste à étudier les mécanismes de transition entre les différentes représentations (physiques, mathématiques, informatiques) des objets géométriques afin d’aboutir à des modèles de représentations à la fois calculables et suffisamment riches pour assurer la certification des résultats produits par les algorithmes. On distingue ici les objectifs algorithmiques (mise en oeuvre, robustesse, complexité) des objectifs mathématiques (concepts, théorèmes pour la certification). La difficulté mathématique et algorithmique des questions posées justifie une collaboration étroite entre mathématiciens et informaticiens, collaboration visant à développer une théorie de l’approximation géométrique.
Partenaires
Universite de Dijon: Frédéric Chazal,
Jérome Saracco, François Blais
INRIA Sophia-Antipolis: Jean-Daniel Boissonnat, Frédéric Cazals, David Cohen-Steiner,
Pierre Alliez, Sylvain Pion
Laboratoire des images et des signaux, Grenoble: Domnique Attali, Francis Lazarus
Ecole normale superieure: Michel Pocchiola, Eric
Colin de Verdière
LMC/IMAG et Dassault Systemes: André Lieutier
Agenda
30 janvier - 3 février 2006: Journées de géométrie algorithmique, Le Bessat (Loire).
22nd Annual ACM Symposium on Computational Geometry June 5-7 2006, Sedona, Arizona : http://www.cs.arizona.edu/~socg06/
Journee GeoTopAl
mardi 26 septembre 2006
ENS Paris
(salle S16, passage saumon, niveau -1
Programme [version imprimable]
10h - 10h30: Robust construction of the extended flow complex.
F. Cazals (INRIA Sophia-Antipolis)
[slides]
10h45 – 11h15: Shape smoothing using double offset.
F. Chazal (INRIA Futurs), D. Cohen-Steiner (INRIA Sophia-Antipolis) et A. Lieutier (Dassault Systèmes)
[slides]
11h45 – 12h15: Surface Tiling through Contouring.
P. Alliez (INRIA Sophia-Antipolis)
[slides]
14h – 14h30: Voronoi diagrams of statistical ditributions.
J.-D. Boissonnat (INRIA Sophia-Antipolis)
[slides]
14h45 – 15h15: Complexité de la triangulation de Delaunay pour des points sur un polyèdre de dimension inférieure à celui de l'espace.
D. Attali (LIS, CNRS Grenoble)
[slides]
15h45 – 16h45: Enveloppes convexes, (pseudo-)triangulations et graphes de visibilité dans les plans topologiques.
M. Pocchiola (ENS Paris)
[slides]
Journees de Geometrie Algorithmique 2007 (12-16 mars 2007)
Centre International de Rencontres Mathématiques, Luminy.
Workshop GeoTopAl
mercredi 23 mai 2007
INRIA Futurs, Parc Club Orsay Université
4, rue Jacques Monod - 91893 ORSAY Cedex
Attention: il faut s'inscrire par email avant le 5 mai 2007
Programme [version imprimable]
09h30 - 10h30 : Distortions et apprentissage automatique 1
R. Nock (Université Antilles-Guyane) slides
11h00 - 12h00 : The power cell algorithm for local homology vineyards
H. Edelsbrunner (Duke University) slides
13h30 - 14h30 : Delaunay Meshing of Piecewise Smooth Complexes
T. K. Dey (Ohio State University) slides (ppt,pdf)
14h45 - 15h45 : Distortions et apprentissage automatique 2
R. Nock (Université Antilles-Guyane) slides
Publications
Articles dans des revues avec comité de lecture
[CFPR06] F. Cazals, J.-C. Faugère, M. Pouget, F. Rouillier, The implicit structure of ridges of a smooth parametric surface, Computer Aided Geometric Design 2006 (to appear).
[CGPZ06] F. Cazals, J. Giesen, M. Pauly, A. Zomorodian, The conformal alpha shapes filtration, The Visual Computer 2006.
[CL06] F. Chazal, A. Lieutier, Stability and computation of topological invariants of solids in Rn, accepted for publication in Discrete & Computational Geometry.
[CLR06] F. Chazal, A. Lieutier, J. Rossignac, Normal-map between normal-compatible manifolds, to appear in Int. Journal of Computational Geometry and Applications.
[CL07] F. Chazal, A. Lieutier, Smooth Manifold Reconstruction from Noisy and Non Uniform Approximation with Guarantees, to appear in Computational Geometry: Theory and Applications (2007).
[CCSL07] F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compact Sets in Euclidean Spaces, to appear in Discrete & Computational Geometry.
[CL08] F. Chazal, A. Lieutier, Smooth Manifold Reconstruction from Noisy and Non Uniform Approximation with Guarantees, in Comp. Geom: Theory and Applications, vol 40(2008) pp 156-170.
[CL07] F. Chazal, A. Lieutier, Stability and computation of topological invariants of solids in $\R^n, Discrete & Computational Geometry, Volume 37, Number 4, pp. 601-617, May 2007.
[CLR07] F. Chazal, A. Lieutier, J. Rossignac, Normal map between normal compatible manifolds, accepted for publication in Int. Journal of Comp. Geometry and Applications.
[CCELW08] Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus et Kim Whittlesey. Splitting (complicated) surfaces is hard. Computational Geometry: Theory and Applications, à paraître.
[CSEH08] David Cohen-Steiner, Herbert Edelsbrunner and John Harer, Extending persistence using Poincaré and Lefschetz duality, Foundations of Computational Mathematics (to appear).
[ACR07] D. Attali, D. Coeurjolly, and E. Remy. Représentation par axe médian. In Hermès, editor, Géométrie discrète et images numériques, série signal et image, ouvrage collectif Chapitre 9. D. Coeurjolly and A. Montanvert and J.-M. Chassery, traité ic2 edition, 2007.
Livres, chapitres de livres
[CFPR06] F. Cazals and J.-C. Faugère and M. Pouget and F. Rouillier, Ridges and umbilics of polynomial parametric surfaces, in Computational Methods for Algebraic Spline Surfaces II, Springer, 2006.
Conférences internationales avec comité de lecture
[BO06] JD. Boissonnat, S. Oudot, Provably Good Sampling and Meshing of Lipschitz Surfaces, Proc. 22th Annu. ACM Sympos. Comput. Geom. 2006.
[CCVELW06] E.W. Chambers, É. Colin de Verdière, J. Erickson, F. Lazarus, K. Whittlesey, Splitting (Complicated) Surfaces is Hard, Proc. ACM Symp. on Computational Geometry (SOCG'06), juin 2006. Version préliminaire dans Proc. European Workshop on Computational Geometry (EWCG'06), mars 2006.
[CL06] F. Chazal, A. Lieutier, Topology Guaranteeing manifold reconstruction using distance function to noisy data, Proc. 22th Annu. ACM Sympos. Comput. Geom. 2006.
[CCSL06] F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compact Sets in Euclidean Spaces, Proc. 22th Annu. ACM Sympos. Comput. Geom. 2006.
[CSEM06] D. Cohen-Steiner, D. Morozov, H. Edelsbrunner, Vines and Vineyards by Updating Persistence in Linear Time, Proc. 22th Annu. ACM Sympos. Comput. Geom. 2006.
[HP06] L. Habert, M. Pocchiola, An homotopy theorem for arrangements of double pseudolines, European Workshop on Computational Geometry (EWCG'06), mars 2006.
[TACSD06] Y. Tong, P. Alliez, D. Cohen-Steiner, M. Desbrun, Designing Quadrangulations with Discrete Harmonic Forms, Symposium on Geometry Processing 2006.
[BPKALB07] M. Botsch, M. Pauly, L. Kobbelt, P. Alliez, B. Levy, S. Bischoff and C. Rössl, Geometric Modeling Based on Polygonal Meshes <http://graphics.ethz.ch/%7Embotsch/publications/sg07-course.pdf> , SIGGRAPH 2007 Course Notes (award for the best course notes).
[ADA07] L. Antani, C. Delage and P. Alliez, Mesh Sizing with Additively Weighted Voronoi Diagrams, 16th International Meshin Roundtable, 2007.
[AEHM07] D. Attali, H. Edelsbrunner, J. Harer, and Y. Mileyko. Alpha-beta Witness complexes. In 10th Workshop on Algorithms and Data Structures, Halifax, Nova Scotia, Canada, August 15-17 2007.
[BWY08] Jean-Daniel Boissonnat, Camille Wormser and Mariette Yvinec, Locally Uniform Anisotropic Meshing, ACM Symosium Computational Geometry 2008.
[CPP08] F. Cazals, A. Parameswaran and S. Pion, Robust construction of the three-dimensional flow complex, ACM Symosium Computational Geometry 2008.
[CL07] F. Cazals, S. Loriot, Computing the exact arrangement of circles on a sphere, with applications in structural biology, Proc. 23th Annu. ACM Sympos. Comput. Geom. Video/Multimedia track, 2007.
[CO08] F. Chazal, S. Oudot, Towards Persistence-Based Reconstruction in Euclidean Spaces, to appear in proc. 2008 ACM Symposium of Computational Geometry.
[CCELLT08] Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus et Shripad Thite. Walking your dog in the woods in polynomial time. Proc. ACM. Symp. on Computational Geometry (SOCG'08), juin 2008, à paraître.
[LT08] A. Lieutier and B. Thibert, Geodesic as limit of geodesics on PL-surfaces, to appear in GMP 2008.
[AAD07] N. Amenta, D. Attali and O. Devillers. Complexity of Delaunay Triangulation for Points on Lower-dimensional Polyhedra. In
Proc. ACM-SIAM Sympos. Discrete Algorithms, New-Orleans,
[ACSTD07] P. Alliez, D. Cohen-Steiner, Y. Tong, and M. Desbrun. Voronoi-based variational reconstruction of unoriented point sets. In Symposium on Geometry Processing, 2007.
[AEM07] D. Attali, H. Edelsbrunner and Y. Mileyko. Weak Witnesses for Delaunay
Triangulations of Submanifolds, in ACM Solid and Physical Modeling 2007.
[BdCSE+07] P. Bendich, d. Cohen-Steiner, H. Edelsbrunner, J. Harer, and D. Morozov. Inferring local homology from sampled stratified spaces. In FOCS, 2007.
[BGO07] J-D. Boissonnat and L. Guibas and S. Oudot, Manifold reconstruction in Arbitrary Dimensions using Witness Complexes, in ACM Symposium Computational Geometry 2007.
[CL07] F. Cazals and S. Loriot. Computing the exact arrangement of circles on a sphere, with applications in structural biology . In Proc. 23th Annu. ACM Sympos. Comput. Geom. Video/Multimedia track, 2007.
[CCSLT07] F. Chazal, D. Cohen-Steiner, A. Lieutier, B. Thibert, Shape Smoothing using Double Offsets, in ACM Solid and Physical Modeling 2007.
Rapports de recherche, articles soumis, thèses, divers
[AEHM06] D. Attali, H. Edelsbrunner, J. Harer, Y. Mileyko, Parametrized Witness Complexes, soumis à SODA 2007.
[AEM06] D. Attali, H. Edelsbrunner, Y. Mileyko, Weak Witnesses for Delaunay Triangulations of Submanifolds, Non encore soumis.
[Caz06] F. Cazals, Robust construction of the extended three-dimensional flow complex, RR 5903 INRIA.
[Oud05] S. Oudot, Sampling and Meshing Surfaces with Guarantees, Thèse de doctorat en sciences, Ecole Polytechnique, 2005.
[Chazal06] F. Chazal, D. Cohen-Steiner, A. Lieutier, B. Thibert, Shape Smoothing using Double Offsets, INRIA Research Report RR-5991, October 2006.
[AEM07] D. Attali, H. Edelsbrunner and Y. Mileyko. Weak Witnesses for Delaunay Triangulations of Submanifolds. Solid and Physical Modeling Symposium,
June 4-6, 2007, Beijing, China. Submitted.
[BGO07] J-D. Boissonnat and L. Guibas and S. Oudot, Manifold reconstruction in Arbitrary Dimensions using Witness Complexes, Submitted to ACM SoCG 2007.
[CPP07] F. Cazals and A. Parameswaran and S. Pion, Robust construction of the extended three-dimensional flow complex, Submitted to ACM SoCG 2007.
[CP07] F. Cazals and M. Pouget, Jet_fitting_3: A Generic C++ Package for Estimating the Differential Properties on Sampled Surfaces via Polynomial Fitting, INRIA Research Report 6093, https://hal.inria.fr/inria-00123501.
[CCSM07] F. Chazal, D. Cohen-Steiner, Q. Mérigot, Stability of Boundary Measures, INRIA Research Report RR-6219, June 2007.
[CCSL07-2] F. Chazal, D. Cohen-Steiner, A. Lieutier, Normal Cone Approximation and Offset Shape Isotopy , INRIA Research Report RR-6100, January 2007.
[BGNC08] B. Bouvier, R. Grunberg, M. Nilges and F. Cazals, Shelling the Voronoi interface of protein-protein complexes predicts residue activity and conservation, INRIA Research Report 6415, 2008.
[CCG08] F. Cazals, F. Chazal and J. Giesen, Spectral Techniques to Explore Point Clouds in Euclidean Space, with Applications in Structural Biology, 2008, submitted.
[CCS07] F. Chazal, D. Cohen-Steiner, Geometric Inference, submitted as a chapter in a book entitled "Tesselations in the Sciences", November 2007.
[LSBPC08] S. Loriot and S. Sachdeva and K. Bastard and C. Prevost and F. Cazals, On the Characterization and Selection of Diverse Conformational Ensembles, 2008, submitted.
Lectures
-
Dominique Attali, David Cohen-Steiner and Herbert Edelsbrunner. Extraction and Simplification of Iso-Surfaces in Tandem.
In Proceedings SGP'05.
- Jean-Daniel Boissonnat and Steve Oudot. Provably good sampling and meshing of surfaces. Graphical Models, 67:405-451, 2005.
- Dominique Attali and Jean-Daniel Boissonnat.
A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces. Discrete and Comp. Geometry, 31:369-384, 2004.
- Dominique Attali and Jean-Daniel Boissonnat. Complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete and Computational Geometry, 30(3):437-452, 2003.
Contacts
Envoyer un e-mail a la liste de diffusion (liste moderee)
Derniere mise a jour: 19 septembre 2008, Pierre Alliez