MathSciDoc: An Archive for Mathematician ∫

We show that the analogue of Hamilton's Ricci flow in the combinatorial setting produces solutions which converge exponentially fast to Thurston's circle packing on surfaces. As a consequence, a new proof of Thurston's existence of circle packing theorem is obtained. As another consequence, Ricci flow suggests a new algorithm to find circle packings.

This goal of the paper is to show that the automorphisms of the complex of curves in a surface are induced by the self-homeomorphisms of the surface except the surface is the 2-holed torus.

Greedy forwarding with geographical locations in a wireless sensor network may fail at a local minimum. In this paper we propose to use conformal mapping to compute a new embedding of the sensor nodes in the plane such that greedy forwarding with the virtual coordinates guarantees delivery. In particular, we extract a planar triangulation of the sensor network with non-triangular faces as holes, by either using the nodes' location or using a landmark-based scheme without node location. The conformal map is computed with Ricci flow such that all the non-triangular faces are mapped to perfect circles. Thus greedy forwarding will never get stuck at an intermediate node. The computation of the conformal map and the virtual coordinates is performed at a preprocessing phase and can be implemented by local gossip-style computation. The method applies to both unit disk graph models and quasi-unit disk graph

We present a novel area-preservation mapping/flattening method using the optimal mass transport technique, based on the Monge-Brenier theory. Our optimal transport map approach is rigorous and solid in theory, efficient and parallel in computation, yet general for various applications. By comparison with the conventional Monge-Kantorovich approach, our method reduces the number of variables from O(n²) to O(n), and converts the optimal mass transport problem to a convex optimization problem, which can now be efficiently carried out by Newton's method. Furthermore, our framework includes the area weighting strategy that enables users to completely control and adjust the size of areas everywhere in an accurate and quantitative way. Our method significantly reduces the complexity of the problem, and improves the efficiency, flexibility and scalability during visualization. Our framework, by combining

We study how to characterize the families of paths between any two nodes s, t in a sensor network with holes. Two paths that can be deformed to one another through local changes are called homotopy equivalent. Two paths that pass around holes in different ways have different homotopy types. With a distributed algorithm we compute an embedding of the network in hyperbolic space by using Ricci flow such that paths of different homotopy types are mapped naturally to paths connecting s with different images of t. Greedy routing to a particular image is guaranteed with success to find a path with a given homotopy type. This leads to simple greedy routing algorithms that are resilient to both local link dynamics and large scale jamming attacks and improve load balancing over previous greedy routing algorithms.

This paper investigates several global rigidity issues for polyhedral surfaces including inversive distance circle packings. Inversive distance circle packings are polyhedral surfaces introduced by P Bowers and K Stephenson in [Mem. Amer. Math. Soc. 170, no. 805, Amer. Math. Soc.(2004)] as a generalization of Andreev and Thurstons circle packing. They conjectured that inversive distance circle packings are rigid. We prove this conjecture using recent work of R Guo [Trans. Amer. Math. Soc. 363 (2011) 47574776] on the variational principle associated to the inversive distance circle packing. We also show that each polyhedral metric on a triangulated surface is determined by various discrete curvatures that we introduced in [arXiv 0612.5714], verifying a conjecture in [arXiv 0612.5714]. As a consequence, we show that the discrete Laplacian operator determines a spherical polyhedral metric.

Surface based 3D shape analysis plays a fundamental role in computer vision and medical imaging. This work proposes to use optimal mass transport map for shape matching and comparison, focusing on two important applications including surface registration and shape space. The computation of the optimal mass transport map is based on Monge-Brenier theory, in comparison to the conventional method based on Monge-Kantorovich theory, this method significantly improves the efficiency by reducing computational complexity from O(n ² ) to O(n). For surface registration problem, one commonly used approach is to use conformal map to convert the shapes into some canonical space. Although conformal mappings have small angle distortions, they may introduce large area distortions which are likely to cause numerical instability thus resulting failures of shape analysis. This work proposes to compose the

Given a compact orientable surface with finitely many punctures \Sigma , let $\Cal S (\Sigma) $ be the set of isotopy classes of essential unoriented simple closed curves in \Sigma . We determine a complete set of relations for a function from $\Cal S (\Sigma) $ to $\bold R $ to be the geodesic length function of a hyperbolic metric with geodesic boundary and cusp ends on \Sigma . As a conse quence, the Teichmller space of hyperbolic metrics with geodesic boundary and cusp ends on \Sigma is reconstructed from an intrinsic $(\bold QP^ 1, PSL (2,\bold Z)) $ structure on $\Cal S (\Sigma) $.

The LaplaceBeltrami operator of a smooth Riemannian manifold is determined by the Riemannian metric. Conversely, the heat kernel constructed from the eigenvalues and eigenfunctions of the LaplaceBeltrami operator determines the Riemannian metric. This work proves the analogy on Euclidean polyhedral surfaces (triangle meshes), that the discrete heat kernel and the discrete Riemannian metric (unique up to a scaling) are mutually determined by each other. Given a Euclidean polyhedral surface, its Riemannian metric is represented as edge lengths, satisfying triangle inequalities on all faces. The LaplaceBeltrami operator is formulated using the cotangent formula, where the edge weight is defined as the sum of the cotangent of angles against the edge. We prove that the edge lengths can be determined by the edge weights unique up to a scaling using the variational approach.

We study the rigidity of polyhedral surfaces using variational principles. The action functionals are derived from the cosine laws. The main focus of this paper is on the cosine law for a nontriangular region bounded by three possibly disjoint geodesics. Several of these cosine laws were first discovered and used by Fenchel and Nielsen. By studying the derivative of the cosine laws, we discover a uniform approach to several variational principles on polyhedral surfaces with or without boundary. As a consequence, the work of Penner, Bobenko and Springborn and Thurston on rigidity of polyhedral surfaces and circle patterns are extended to a very general context.