{"id":333,"date":"2015-11-03T15:09:58","date_gmt":"2015-11-03T14:09:58","guid":{"rendered":"https:\/\/project.inria.fr\/jga2015\/?page_id=333"},"modified":"2016-01-07T10:41:03","modified_gmt":"2016-01-07T09:41:03","slug":"exposes","status":"publish","type":"page","link":"https:\/\/project.inria.fr\/jga2015\/exposes\/","title":{"rendered":"Expos\u00e9s"},"content":{"rendered":"<ul>\n<li style=\"text-align: justify;\"><strong>Olivier Devillers<br \/>\n<\/strong><em>Analyse en moyenne de la marche par visibilit\u00e9<strong><br \/>\n<\/strong><span id=\"MathJax-Element-1-Frame\" class=\"MathJax\"><span id=\"MathJax-Span-1\" class=\"math\"><span id=\"MathJax-Span-2\" class=\"mrow\"><span id=\"MathJax-Span-8\" class=\"mo\"><\/span><\/span><\/span><\/span><\/em><u>R\u00e9sum\u00e9<\/u> : Nous montrons que les algorithmes de routage sans m\u00e9moire de marche gloutonne, de marche au compas et toutes les variantes de marche par visibilit\u00e9 sont asymptotiquement optimale en moyenne pour la triangulation de Delaunay. Plus pr\u00e9cis\u00e9ment, nous consid\u00e9rons la triangulation de Delaunay d&rsquo;un processus de Poisson non born\u00e9 d&rsquo;intensit\u00e9 un et d\u00e9montrons que le rapport entre les nombre d&rsquo;\u00e9tapes du pire et du meilleur chemin entre deux sommets suffisamment loin dans un domaine d&rsquo;aire <span id=\"MathJax-Element-4-Frame\" class=\"MathJax\"><span id=\"MathJax-Span-21\" class=\"math\"><span id=\"MathJax-Span-22\" class=\"mrow\"><span id=\"MathJax-Span-23\" class=\"mi\">n<\/span><\/span><\/span><\/span> est born\u00e9 par une constante avec une probabilit\u00e9 convergeant vers 1. On en d\u00e9duit comme corollaire que le pire chemin a au plus <span id=\"MathJax-Element-5-Frame\" class=\"MathJax\"><span id=\"MathJax-Span-24\" class=\"math\"><span id=\"MathJax-Span-25\" class=\"mrow\"><span id=\"MathJax-Span-26\" class=\"mi\">O<\/span><span id=\"MathJax-Span-27\" class=\"mo\">(<\/span><span id=\"MathJax-Span-28\" class=\"msqrt\"><span id=\"MathJax-Span-29\" class=\"mrow\"><span id=\"MathJax-Span-30\" class=\"mi\">n<\/span><\/span>\u221a<\/span><span id=\"MathJax-Span-32\" class=\"mo\">)<\/span><\/span><\/span><\/span> \u00e9tapes. Ce r\u00e9sultat a des applications au routage dans les r\u00e9seaux mobiles et r\u00e9ponds \u00e0 une conjecture sur les algorithmes de localisation par marche dans les triangulations. Nos d\u00e9monstrations utilisent des r\u00e9sultats de percolation et de g\u00e9om\u00e9trie stochastique<em><br \/>\n<\/em><\/li>\n<li style=\"text-align: justify;\"><strong>Vincent Despr\u00e9<\/strong><br \/>\n<span style=\"color: #333333;\"><span style=\"color: #333333;\"><em>Computing Geometric Intersection Numbers<br \/>\n<\/em><u>R\u00e9sum\u00e9<\/u> : <\/span><\/span>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.<span style=\"color: #333333;\"><em><br \/>\n<\/em><\/span><\/li>\n<li style=\"text-align: justify;\"><strong>Marc Pouget<\/strong><br \/>\n<span style=\"color: #333333;\"><span style=\"color: #333333;\"> <em>Projection of a Smooth Space Curve: Numeric and Certified Topology Computation<br \/>\n<\/em><\/span><\/span><\/p>\n<div><u>R\u00e9sum\u00e9<\/u> : Let a plane curve be defined as the projection of the intersection of two implicit surfaces or as the apparent contour of a surface. \u00a0Generically 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. \u00a0We 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.<br \/>\n<a href=\"https:\/\/project.inria.fr\/jga2015\/files\/2015\/11\/pouget-jga15.pdf\">Transparents \/ slides<\/a><\/div>\n<\/li>\n<li style=\"text-align: justify;\">\n<div><strong>Arnaud de Mesmay<\/strong><br \/>\n<em>Almost optimally cutting a surface into a disk<\/em><br \/>\n<u>R\u00e9sum\u00e9<\/u> : 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.<br \/>\nBased on joint work with Vincent Cohen-Addad<\/div>\n<\/li>\n<li style=\"text-align: justify;\"><strong>Alba Chiara de Vitis<\/strong><br \/>\n<em>Learning a Mixture of Distributions using Concentration of Measure<\/em><\/li>\n<li style=\"text-align: justify;\"><strong>Nicolas Mellado<\/strong><br \/>\n<em>Fast Global Pointcloud Registration<\/em><br \/>\n<u>R\u00e9sum\u00e9<\/u> : 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.<br \/>\n<a href=\"http:\/\/www.irit.fr\/~Nicolas.Mellado\/research\/projects\/super4pcs\/globalmatching_mellado_JGA2015.pdf\"><span style=\"color: #d6341d;\">Transparents \/ slides<\/span><\/a><\/li>\n<li style=\"text-align: justify;\"><strong>Manish Mandad<\/strong><br \/>\n<em>Robust Mappings Between Surfaces<br \/>\n<\/em><u>R\u00e9sum\u00e9<\/u> : 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.<em><br \/>\n<\/em><\/li>\n<li style=\"text-align: justify;\"><strong>Mael Rouxel-Labbe<\/strong><br \/>\n<em>Anisotropic mesh generation<\/em><br \/>\n<u>R\u00e9sum\u00e9<\/u> : 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.<\/li>\n<li style=\"text-align: justify;\"><strong>Tuong-Bach Nguyen<\/strong><br \/>\n<em><em>Le recouvrement \u00e0 epsilon pr\u00e8s d\u2019un ensemble est NP-complet<br \/>\n<\/em><\/em><u>R\u00e9sum\u00e9<\/u> : Soit S un ensemble de R\u00b2, epsilon un r\u00e9el positif, S+ et S- respectivement le dilat\u00e9 et l&rsquo;\u00e9rod\u00e9 de S par une boule de rayon epsilon. On appelle recouvrement \u00e0 epsilon pr\u00e8s de S tout ensemble fini de boules dont l&rsquo;union contient S- et est contenue dans S+. Si S est lui-m\u00eame une union finie de boules, nous montrons que le probl\u00e8me de d\u00e9cision consistant \u00e0 d\u00e9terminer s\u2019il existe un recouvrement \u00e0 epsilon pr\u00e8s de S de taille plus petite qu\u2019un nombre entier donn\u00e9 est NP-complet. Notre d\u00e9monstration est bas\u00e9e sur une r\u00e9duction \u00e0 partir du probl\u00e8me de couverture d\u2019un graphe par sommets (vertex cover).<\/li>\n<li style=\"text-align: justify;\"><strong>Siargey Kachanovich<\/strong><br \/>\n<em>Greedy construction of protected sets<br \/>\n<\/em><u>R\u00e9sum\u00e9<\/u> : A finite set of points in a d-dimensional metric space is called \u03b4-protected if it contains no subset of d+2 points\u00a0 \u03b4-close to be cospherical. Given a constant \u03b4, we present a greedy algorithm that samples the d-dimensional flat torus and produces a \u03b4-protected net.<em><br \/>\n<\/em><\/li>\n<li style=\"text-align: justify;\"><strong>Etienne Corman<\/strong><br \/>\n<em>Continuous Matching via Vector Field Flow<br \/>\n<\/em><u>R\u00e9sum\u00e9<\/u> : We present a new method for non-rigid shape matching designed to enforce continuity of the resulting correspondence. Our method is\u00a0based 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.<em><br \/>\n<\/em><\/li>\n<li style=\"text-align: justify;\"><strong>Mathieu Carri\u00e8re<\/strong><br \/>\n<em><em>A Theoretical Framework for 1D Mapper<br \/>\n<\/em><\/em><u>R\u00e9sum\u00e9<\/u> : 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.<br \/>\n<a href=\"http:\/\/arxiv.org\/abs\/1511.05823\">Transparents \/ slides<br \/>\nLien vers article \/ link to article<\/a><\/li>\n<li style=\"text-align: justify;\"><strong>Harry Lang<\/strong><br \/>\n<em>Facility Location Methods for Clustering Problems<br \/>\n<\/em><u>R\u00e9sum\u00e9<\/u> : 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). \u00a0In this talk, we will introduce the OFL algorithm and discuss its applications. \u00a0Current research includes applying OFL to construct streaming epsilon-nets on manifolds, and\u00a0show 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).<em><br \/>\n<\/em><\/li>\n<li style=\"text-align: justify;\"><strong>Jingjing Shen<br \/>\n<\/strong><em><em>Convert trimmed NURBS surfaces to subdivision surfaces<strong><br \/>\n<\/strong><\/em><\/em><u>R\u00e9sum\u00e9<\/u> : 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$.<em><strong><br \/>\n<\/strong><\/em><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<ul>\n<li style=\"text-align: justify;\"><strong>Olivier Devillers<br \/> <\/strong><em>Analyse en moyenne de la marche par visibilit\u00e9<strong><br \/> <\/strong><\/em><u>R\u00e9sum\u00e9<\/u> : Nous montrons que les algorithmes de routage sans m\u00e9moire de marche gloutonne, de marche au compas et toutes les variantes de marche par visibilit\u00e9 sont asymptotiquement optimale en moyenne pour la triangulation de  \u2026\n<p class=\"continue-reading-button\"> <a class=\"continue-reading-link\" href=\"https:\/\/project.inria.fr\/jga2015\/exposes\/\">Lire la suite<i class=\"crycon-right-dir\"><\/i><\/a><\/p>\n","protected":false},"author":45,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-333","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/pages\/333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/users\/45"}],"replies":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/comments?post=333"}],"version-history":[{"count":21,"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/pages\/333\/revisions"}],"predecessor-version":[{"id":391,"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/pages\/333\/revisions\/391"}],"wp:attachment":[{"href":"https:\/\/project.inria.fr\/jga2015\/wp-json\/wp\/v2\/media?parent=333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}