- Olivier Devillers
Analyse en moyenne de la marche par visibilité
Résumé : Nous montrons que les algorithmes de routage sans mémoire de marche gloutonne, de marche au compas et toutes les variantes de marche par visibilité sont asymptotiquement optimale en moyenne pour la triangulation de Delaunay. Plus précisément, nous considérons la triangulation de Delaunay d’un processus de Poisson non borné d’intensité un et démontrons que le rapport entre les nombre d’étapes du pire et du meilleur chemin entre deux sommets suffisamment loin dans un domaine d’aire n est borné par une constante avec une probabilité convergeant vers 1. On en déduit comme corollaire que le pire chemin a au plus O(n√) étapes. Ce résultat a des applications au routage dans les réseaux mobiles et réponds à une conjecture sur les algorithmes de localisation par marche dans les triangulations. Nos démonstrations utilisent des résultats de percolation et de géométrie stochastique
- Vincent Despré
Computing Geometric Intersection Numbers
Résumé : The geometric intersection number of a curve on a surface is the minimal number of self-intersections of any homotopic curve, i.e. of any curve obtained by continuous deformation. Likewise, the geometric intersection number of a pair of curves is the minimal number of intersections of any homotopic pair. Given two curves represented by closed walks of length at most l on a combinatorial surface of complexity n we describe simple algorithms to compute the geometric intersection number of each curve or of the two curves in O(n+ l^2) time. We also propose an algorithm of complexity O(n+l.log^2(l)) to decide if the geometric intersection number of a curve is zero, i.e. if the curve is homotopic to a simple curve.
- Marc Pouget
Projection of a Smooth Space Curve: Numeric and Certified Topology Computation
Résumé : Let a plane curve be defined as the projection of the intersection of two implicit surfaces or as the apparent contour of a surface. Generically its singularities are nodes, or nodes and ordinary cusps for an apparent contour. State-of-the-art numerical algorithms compute the topology of smooth curves but usually fail to certify the topology of singular ones. The main challenge is to find practical numerical criteria that guarantee the existence and the uniqueness of a singularity inside a given box. We propose two approaches to this problem. One is based on subresultants yielding a system in 2D characterizing the singularities, while the other yields a system in 4D, which solutions project to the singularities. Both systems are square (as many equations as unknown) and regular (solutions of multiplicity 1) which enables to solve them with a subdivision method with certification provided by interval analysis.
Transparents / slides -
Arnaud de Mesmay
Almost optimally cutting a surface into a disk
Résumé : Given a graph embedded on a surface, a natural problem is to cut the surface along a subgraph so as to obtain a disk. This is useful both for applications (computer graphics, parameterization) or theoretical algorithms, where this allows to apply techniques designed for planar graphs. The length of the cut-graph is a key factor in both cases, as it will quantify how much this cutting distorted the input. While finding the shortest possible cut-graph is NP-hard, it is natural to look for algorithms which behave nicely for small genus, as in many practical cases the genus is quite small. In this work I will describe an arbitrarily good approximation algorithm that runs in time fixed parameter tractable with respect to the genus of the surface.
Based on joint work with Vincent Cohen-Addad - Alba Chiara de Vitis
Learning a Mixture of Distributions using Concentration of Measure - Nicolas Mellado
Fast Global Pointcloud Registration
Résumé : Data acquisition in large-scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. First approaches tackling this problem have been designed using RANdom SAmple Consensus (RANSAC) schemes. In a nutshell, triplets of congruent points are pseudo-randomly selected on each cloud, a geometric transformation is estimated between these triplets, applied on one cloud, and the registration error reported. The algorithm stops when the registration error is below a given threshold, or when all the configurations have been explored. In practice, the cubic time complexity of the RANSAC scheme vastly limits its applicability to large point clouds. Recently, the 4-Points Congruent Set (4PCS) algorithm and its variant Super4PCS have been proposed to rigidly register two clouds with respectively quadratic and linear time complexity. In this talk, we will review the successive changes from RANSAC to Super4PCS, and explore the most promising research directions for global point cloud registration.
Transparents / slides - Manish Mandad
Robust Mappings Between Surfaces
Résumé : We address the problem of mapping between two surfaces, with focus on robustness to both imperfect data and heterogeneous representations. In our approach the bijectivity and continuity of the mapping are sought after through a novel variational formulation based on optimal transportation and geodesic variance minimization of the associated transport plan. Intuitively, we reformulate the notion of homeomorphism between surfaces by optimizing for mappings that map geodesic neighborhoods to small geodesic neighborhoods. Optimization is achieved through a multi-scale expectation-minimization approach, combined with diffusion distances and Sinkhorn iterations to efficiently approximate geodesic distances and optimal transport plans.
- Mael Rouxel-Labbe
Anisotropic mesh generation
Résumé : Anisotropic simplicial meshes are triangulations with elements elongated along prescribed directions. Anisotropic meshes have been shown to be well suited for interpolation of functions or solving PDEs. They can also significantly enhance the accuracy of a surface representation. Given a domain D endowed with a metric tensor field, we propose new approaches to generate an anisotropic mesh that approximates D with elements shaped according to the metric field. Each approach is based on a different definition of the anisotropic distance. We compare the results and investigate some optimization techniques. - Tuong-Bach Nguyen
Le recouvrement à epsilon près d’un ensemble est NP-complet
Résumé : Soit S un ensemble de R², epsilon un réel positif, S+ et S- respectivement le dilaté et l’érodé de S par une boule de rayon epsilon. On appelle recouvrement à epsilon près de S tout ensemble fini de boules dont l’union contient S- et est contenue dans S+. Si S est lui-même une union finie de boules, nous montrons que le problème de décision consistant à déterminer s’il existe un recouvrement à epsilon près de S de taille plus petite qu’un nombre entier donné est NP-complet. Notre démonstration est basée sur une réduction à partir du problème de couverture d’un graphe par sommets (vertex cover). - Siargey Kachanovich
Greedy construction of protected sets
Résumé : A finite set of points in a d-dimensional metric space is called δ-protected if it contains no subset of d+2 points δ-close to be cospherical. Given a constant δ, we present a greedy algorithm that samples the d-dimensional flat torus and produces a δ-protected net.
- Etienne Corman
Continuous Matching via Vector Field Flow
Résumé : We present a new method for non-rigid shape matching designed to enforce continuity of the resulting correspondence. Our method is based on the recently proposed functional map representation, which allows efficient manipulation and inference but often fails to provide a continuous point-to-point mapping. We address this problem by exploiting the connection between the operator representation of mappings and flows of vector fields. In particular, starting from an arbitrary continuous map between two surfaces we find an optimal flow that makes the final correspondence operator as close as possible to the initial functional map. Our method also helps to address the symmetric ambiguity problem inherent in many intrinsic correspondence methods when matching symmetric shapes.
- Mathieu Carrière
A Theoretical Framework for 1D Mapper
Résumé : Mapper algorithm is a famous tool in Topological Data Analysis. In short, it allows to represent the topology of high dimensional data in the form of simplicial complexes through a covering of the image of some filter function defined on the data. In this talk, I will present recent progresses in the theoretical treatment of the classical Mapper algorithm. In particular, I will present its extension with simplicial posets, the so-called MultiNerve Mapper, that greatly alleviates the mathematical framework that is necessary to derive theoretical guarantees on the output. Formal treatments with schemes of proofs will be discussed, such as the connections with Reeb graphs for instance. I will also introduce a measure of dissimilarity between the MultiNerve Mapper objects, that is similar to the bottleneck distance, leading to stability results, while taking the covering into account. Finally, I will present different possible ways to implement the algorithm in the discrete case.
Transparents / slides
Lien vers article / link to article - Harry Lang
Facility Location Methods for Clustering Problems
Résumé : The OFL (online facility location) algorithm of Meyerson has been used extensively to provide low-space solutions to a variety of clustering problems (k-median, k-means, etc). In this talk, we will introduce the OFL algorithm and discuss its applications. Current research includes applying OFL to construct streaming epsilon-nets on manifolds, and show a prior application of OFL to problem of k-median clustering on streaming data (in the streaming model, points arrive sequentially and only a sublinear-sized subset may be stored in memory).
- Jingjing Shen
Convert trimmed NURBS surfaces to subdivision surfaces
Résumé : CAD models generally consist of multiple NURBS patches, both trimmed and untrimmed. There is a long-standing challenge that trimmed NURBS patches cause unavoidable gaps in the model. We address this by converting multiple NURBS patches to a single untrimmed NURBS-compatible subdivision surface in a three stage process. First, for each patch, we generate in domain space a quadrangulation that follows boundary edges of the patch and respects the knot spacings along edges. Second, the control points of the corresponding subdivision patch are computed in model space. Third, we merge the subdivision patches across their common boundaries to create a single subdivision surface. The converted model is gap-free and can maintain inter-patch continuity up to $C^2$.
