Title: Mappings and Meshes: connections between continuous and discrete geometry (I and II)
I will give two lectures about some interactions between conformal, hyperbolic and computational geometry. The first lecture shows how ideas from discrete and computational geometry can help compute conformal mappings, and the second lecture reverses the direction and shows how conformal maps can give meshes of polygonal domains with optimal geometry.
Lecture 1: The conformal map from the unit disk to the interior of a polygon P is given by the Schwarz-Christoffel formula, but this is stated in terms of parameters that are hard to compute from P. After some background and motivation, I explain how the medial axis of a domain, a concept from computation geometry, can be used to give a fast approximation to these parameters, with bounds on the accuracy that are independent of P. The precise statement involves quasiconformal mappings, and proving these bounds uses a result about hyperbolic convex sets originating in Thurston's work on 3-manifolds.
Lecture 2: I will show how conformal maps can be used to give meshes with sharp angle bounds on the mesh elements. For example: (1) every polygon P has a linear sized quad-mesh with all angles between 60 and 120 degrees (except at smaller angles of P), (2) every polygon has an acute triangulation and the optimal upper angle bound can be computed for each P, (3) every planar straight line graph (PSLG) has a conforming acute triangulation of polynomial complexity. In addition to conformal mappings, we also use some ideas from dynamics (a discrete closing lemma) and Riemann surfaces (the thick-thin decomposition).
Title: Geometry Processing with Intrinsic Triangulations
The intrinsic viewpoint was a hallmark of 19th century geometry, enabling one to reason about shapes without needing to consider an embedding in space—and leading to major developments in the 20th century such as Einstein’s theory of general relativity. Yet 21st century digital geometry processing still largely adopts an extrinsic mindset, where the geometry of a polyhedral surface is expressed via vertex positions in n-dimensional space. This talk explores how the intrinsic view of polyhedral surfaces helps relax some standard assumptions in geometric computing, leading to algorithms that are more flexible and numerically more robust. In particular we will examine fundamental data structures for intrinsic triangulations, extensions of important triangulation algorithms to curved surfaces, as well as methods for finite element problems, finding geodesics, and computing discrete conformal maps.
Title: Orthogonal ring patterns
We introduce orthogonal ring patterns consisting of pairs of concentric circles generalizing circle patterns. We show that orthogonal ring patterns in euclidean and hyperbolic planes and in a sphere are governed by integrable equations. We deliver variational principles generalizing the corresponding variational principles for circle patterns. These are used to prove existence and uniqueness results, and also to compute ring patterns with classical boundary conditions. Relation to generalized Koebe polyhedra touching two spheres is presented. The later are used to generate discrete cmc surfaces.
Title: The deformation space of geodesic triangulations and Tutte’s embedding
The deformation space of geodesic triangulations of a Riemannian surface $S$ can be regarded as a finite dimensional analogue to the group of surface diffeomorphisms of $S$. It is a natural question whether they have the same homotopy type. In 1984, Bloch, Connelly, and Henderson proved that the space of geodesic triangulations of a convex polygon is homeomorphic to some Euclidean space and thus is contractible. So they gave a positive answer to this question in the case of convex polygons. In this talk, we will relate this problem to Tutte’s spring theorem, and prove that the deformation space of geodesic triangulations of a closed Riemannian surface of negative curvature is contractible. This confirms a conjecture by Connelly, Henderson, Ho, Starbird in 1983. The main idea of the proof is to generalize Tutte’s spring theorem to closed surfaces of negative curvature. We will discuss the application of (generalied) Tutte’s spring theorem in image morphing. This is a joint work with Tianqi Wu and Xiaoping Zhu.
Title: Canonical cell decompositions for punctured real projective surfaces
Cooper and Long generalised the canonical cell decoposition of decorated cusped hyperbolic manifolds of finite volume to the setting of real projective geometry. In this talk, I will describe an edge-flipping calgorithm that computes these decompositions for punctured surfaces using Fock and Goncharov’s A-coordinates. If time permits, I will also outline how this setting allows us to show that the moduli space of doubly-decorated convex projective structures of finite volume on punctured surfaces has a natural cell decomposition of this space that is invariant under the action of the mapping class group. This generalises a result of Penner concerning decorated Teichmüller space. All of this is join work with Robert Haraway, Robert Löwe and Dominic Tate.
Title: Rigidity and deformation of discrete conformal structures on polyhedral surfaces
Discrete conformal structure on polyhedral manifolds is a discrete analogue of the conformal structure on Riemannian manifolds, which assigns the discrete metrics by scalar functions defined on the vertices. There are several different types of discrete conformal structures on surfaces, including the tangential circle packing, Thurston's circle packing, inversive distance circle packing and vertex scaling. Most of these discrete conformal structures were invented and studied individually in the past. The generic notion of discrete conformal structures on polyhedral surfaces was introduced recently independently by Glickenstein and Thomas from Riemannian geometry perspective and by Zhang-Guo-Zeng-Luo-Yau-Gu from Bobenko-Pinkall-Springborn's observation on the relationships of vertex scaling on polyhedral surfaces and 3-dimensional hyperbolic geometry, which includes the existing discrete conformal structures as special cases. In this talk, we will report some recent progress on rigidity and deformation of generic discrete conformal structures on polyhedral surfaces.
Title: The Bilaplacian on polyhedral surfaces — theory and applications
Laplace operators have been studied extensively on polyhedral surfaces and remain to be one of the central building blocks for geometry processing applications. In this talk we will focus on the Bilaplacian, which poses additional challenges when it comes to convergence analysis. In particular, we will consider a popular discretization of the Bilaplacian on polyhedral surfaces — the mixed finite element cotangent discretization — and investigate its convergence under mesh refinement. Our convergence result generalizes the case of planar domains that was investigated by Scholz in 1978. We are also going to look at some applications of the Bilaplacian in geometry processing, such as interpolation, smoothing, character animation, and more. This is joint work with Oded Stein, Eitan Grinspun, and Alec Jacobson.
Title: Parametetizarion-based remeshing for mesh realization
In many applications, such as architecture and stylized fabrication, practitioners construct a real world counterpart of a discrete surface (a realization). Often, this realization is done by decomposing the surface into smaller elements, which are then assembled to obtain the final shape. In this talk, we will consider the problem of surface realization in the context of semi-regular surface remeshing using a (griddable) parameterization approach. We will consider the following question: under which conditions can two (discrete) tangent vector fields be integrated into a griddable parameterization? We will present two approaches to the solution, and corresponding applications for mesh realization.
Title: A discrete spherical Laplacian
I will survey the motivation and generalizations of the cotangent Laplacian and introduce a discrete Laplacian associated with surfaces made out of spherical triangles. The definition is motivated by the theory of mixed volumes. The same theory provides a spectral property of the discrete spherical Laplacian.
Title: Convergence results for discrete conformal maps based on conformally equivalent triangular lattices and circle patterns
Discrete conformal maps as discrete analogues of smooth conformal maps may be defined in several ways. In my talk, I restrict myself to two notions of discrete conformality for mapping in the complex plane, namely circle patterns and conformally equivalent triangulations. The question of convergence establishes an important link between corresponding smooth and discrete notions. I present three approximation results which make this connection more explicit. Two results study discrete conformal maps obtained from Dirichlet boundary conditions. The third convergence claim is based on sequences of embedded circle patterns which approximate two given (bounded) simply connected domains.
Title: Computational theory of graphs, sets and rigid sets
Quotient spaces are a natural mathematical tool to describe a variety of algorithmic problems where different objects are to be compared while their natural symmetries are to be ignored. In particular, we will focus on graphs and sets whose symmetries are permutation of the vertices, and rigid sets whose symmetries also include rigid motions. All three data types are prevalent in computer vision/graphics and in many other applications.
We will discuss two problems involving these data types: (1) Geometric alignment of graphs/sets/rigid sets, and whether it can be done in polynomial time. (2) Neural network architectures which are invariant to the symmetries of graphs/sets/rigid sets, and whether they are universal (can approximate every invariant continuous function). For both problems we will see that they are tractable for sets and intractable for graphs. We will then explain why rigid sets are an intermediate case, where high dimensional rigid sets are equivalent in graphs in terms of complexity, while for fixed low dimension they are tractable. The focus on the lecture will be on two papers which leverage these insights to achieve tractable algorithms for low-dimensional rigid sets, both for geometric alignment and for invariant neural networks.