G E O M E T R I C A (INRIA Project-team)

Algebraic topology and sensor networks

by Anaïs Vergne (Télécom ParisTech)

Time and location: Tuesday April 23 @ 2:30pm, INRIA Saclay (Salle Grace Hopper)

Abstract: Wireless sensor networks are more and more widespread in fields which range from environmental monitoring to battlefield surveillance or cattle enumeration in agriculture. The main quality of service expected from a wireless sensor network is its topology: the connectivity to forward data to a central hub, and the coverage to oversee an entire area. In order to overcome the problems that arise from disconnectivity or coverage holes, sensors are spread in an excessive number. However, this is cost consuming in terms of hardware but also of battery life. Indeed, sensors are not plugged in and the lifespan of the network depends on the lifespan of each battery. We propose an algorithm, based on the simplicial homology representation of sensor networks, which gives which sensor to put on stand by in order to reduce power consumption while keeping the same topology. Secondly, we will discuss the behaviour of the size of the greatest number of completely connected sensors in function of percolation regimes. In graph theory, this is known as the clique number of a random geometric graph. We give its asymptotically almost sure behaviour when the number of points tends to infinity.

On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions

by Natan Rubin (Freie Universität Berlin)

Time and location: Wednesday April 17 @ 3:00pm, INRIA Saclay (Salle Philippe Flajolet)

Abstract: Let P be a collection of n points in the plane, each moving along some straight line and at unit speed.
 We obtain an almost tight upper bound of O(n^(2+epsilon)), for any epsilon>0, on the maximum number of discrete changes that the Delaunay triangulation DT(P) of P experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that
 (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions.

Can Mean-Curvature Flow be Modified to be Non-singular?

by Mirela Ben Chen (Technion - Israel Institute of Technology)

Time and location: Wednesday March 20  @ 2:00pm, INRIA Saclay (Salle Grace Hopper)

Abstract: This work considers the question of whether mean-curvature flow can be modified to avoid the formation of singularities. We analyze the finite-elements discretization and demonstrate why the original flow can result in numerical instability due to division by zero. We propose a variation on the flow that removes the numerical instability in the discretization and show that this modification results in a simpler expression for both the discretized and continuous formulations. We discuss the properties of the modified flow and present empirical evidence that not only does it define a stable surface evolution for genus-zero surfaces, but that the evolution converges to a conformal parameterization of the surface onto the sphere.

Rigidity of Infinite Hexagonal Triangulation of Plane.

by Jian Sun (Mathematical Sciences Center, Tsinghua University)

Time and location: Thursday January 31  @ 2:00pm, INRIA Saclay (Salle Grace Hopper)

Abstract: In this talk,  I will describe the concept of PL conformal transformation of the metric on triangulated surfaces, and present our recent result on the rigidity of the infinite hexagonal triangulation of the plane under PL conformal transformation.
This is the joint work with Tianqi Wu, Feng Luo and David Xianfeng Gu.

The Landscape of Complex Networks.

by Yuan Yao (School of Mathematical Sciences, Peking University)

Time and location: Tuesday January 22  @ 1:30pm, INRIA Saclay (Salle Marcel-Paul Schützenberger)

Abstract: We extend the notion of the ``free energy landscape'' commonly used in physics and other areas of physical sciences to networks.  This extension enables us to perform critical point analysis of functions defined on networks and identify important structural components of the network.  We demonstrate how these tools can be used to identify ``metastable saddle'' states in a protein structure network as well as ``bridge nodes'' between communities in a social network.

This is a joint work with Weinan E, Jianfeng Lu, and Yaning Liu.

Numerical optimization of an eigenvalue of the Laplacian on a domain in surfaces.

by Régis Straubhaar (Université de Neuchâtel)

Time and location: Wednesday January 9  @ 10:00am, INRIA Saclay (Salle Marcel-Paul Schützenberger)

Abstract: Let (M, g) be a smooth and complete surface, let Ω ⊂ M be a domain in M, and let Δ_g be the Laplace operator on M. The spectrum of the Dirichlet-Laplace operator on Ω is a sequence 0 < λ₁(Ω) ≤ λ₂(Ω) ≤ ... ↗ ∞. A classical question is to find which domain Ω^* minimizes λ_k(Ω) among all domain of a given area, and to find the value of the corresponding λ_k(Ω^*). In this talk, we will go through the classical case M = ℝ², in which theoretical results are known for the first and second eigenvalues as well as numerical experimentations for higher eigenvalues. Then, we will investigate numerically the case where M is the sphere, the hyperbolic disc and a hyperboloid, in order to consider various curvature. The algorithm, using shape optimization and based on the finite element method to find an approximation of a candidate for Ω^*, will be presented and discussed.