FRG Workshop on Geometric Methods for Analyzing Discrete Shapes

This workshop will take place May 7-9 (Friday-Sunday), 2021 virtually on Zoom

The aim of the workshop is to bring together a community of researchers in mathematics, computer science and data science who develop theoretical and computational models to characterize shapes and analysis of image data.

This workshop is part of the NSF FRG project: Geometric and Topological Methods for Analyzing Shapes.

The first half of the workshop will feature talks aimed at graduate students, newcomers and broad spectrum of audiences. Christopher Bishop (Stony Brook) and Keenan Crane (Carnegie Mellon) will each give two featured talks. The remaining part will have both background and research talks. There will also be organized discussions of open problems and potential applications.

For the discussions, we are soliciting open problems in mathematical theory and applications of shape analysis. You are encouraged to post problems by sending an email to geometricproblemsfrg@gmail.com.

We invite junior researchers to present a short talk in the workshop. The session will be held on Friday, May 7th or Saturday, May 8th at 4pm and are expected to be 15-20 minutes in length. It is a great opportunity to share your work and get to know others at the workshop. Depending on the number of contributed talks, the organizers will review the submissions and let you know if you have been selected. If you are interested please send your title and abstract to tianqi@cmsa.fas.harvard.edu by the end of May 2nd.

Register here to attend this event

Organizers:

  • David Glickenstein, University of Arizona
  • Joel Hass, University of California, Davis
  • Patrice Koehl, University of California, Davis
  • Feng Luo, Rutgers University, New Brunswick
  • Tianqi Wu, Harvard University
  • Shing-Tung Yau, Harvard University

Featured lectures:

  • Christopher Bishop, Stony Brook
  • Keenan Crane, Carnegie Mellon

Speakers include:

  • Miri Ben-Chen, Technion – Israel Institute of Technology
  • Alexander Bobenko, Technische Universität Berlin, Germany
  • Ulrike Buecking, Free University, Germany
  • Nadav Dym, Duke University
  • Ivan Izmestiev, Vienna University of Technology
  • Yanwen Luo, Rutgers
  • Stephan Tillmann, The University of Sydney
  • Max Wardetzky, University of Goettingen 
  • Xu Xu, Wuhan University

Schedule (Eastern Daylight Time)

Friday, May 7:

TimeSpeakerTitle/Abstract
11:00 – 11:05am ETWelcome Opening by Joel Hass
11:05 – 12:05pmChristopher Bishop

Video
Title: Mappings and Meshes: connections between continuous and discrete geometry I

Abstract: 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.
12:15 – 1:15pmKeenan Crane

Video
Title: Geometry Processing with Intrinsic Triangulations I

Abstract: 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.
1:30 – 2:30pmAlexander BobenkoTitle: Orthogonal ring patterns

Abstract: 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.
2:45 – 3:45pmBreak
4:00 – 5:00pmContributed Talks
(abstracts)
Hana Dal Poz Kourimska: (Video) Uniformization with a new discrete Gaussian curvature
Hasan Pourmahmood-Aghababa: (Video) Orientation-Preserving Vectorized Distance Between Curves
Xiaoping Zhu: (Video) Convergence of discrere unformization factors on closed surfaces
5:15 – 6:15pmYanwen Luo

Video
Title: The deformation space of geodesic triangulations and Tutte’s embedding

Abstract: 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.
6:30 – 7:30pmStephan Tillmann

Video
Title: Canonical cell decompositions for punctured real projective surfaces

Abstract: 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.
7:45 – 8:45pmXu Xu

Video
Title: Rigidity and deformation of discrete conformal structures on polyhedral surfaces

Abstract: 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.

Saturday, May 8

TimeSpeakerTitle/Abstract
11:00 – 12:00pmChristopher Bishop

Video
Title: Mappings and Meshes: connections between continuous and discrete geometry II

Abstract: 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 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).
12:15 – 1:15pmKeenan Crane

Video
Title: Geometry Processing with Intrinsic Triangulations II

Abstract: 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.
1:30 – 2:30pmMax Wardetzky

Video
Title: The Bilaplacian on polyhedral surfaces — theory and applications

Abstract: 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.
2:45 – 3:45pmContributed Talks
(abstracts)
Emil Saucan: (Video) Geometric Persistent Homology for networks and hypernetworks
Matteo Raffaelli: (Video) Nonrigidity of flat ribbons
Matthijs Ebbens: (Video) Minimal Delaunay triangulations of hyperbolic surfaces
4:00 – 5:00pmProblems and applications discussion

Sunday, May 9

TimeSpeakerTitle/Abstract
11:00 – 12:00pmMiri Ben-Chen

Video
Title: Parametetizarion-based remeshing for mesh realization

Abstract: 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.
12:15 – 1:15pmIvan Izmestiev

Video

Title: A discrete spherical Laplacian

Abstract: 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.
1:30 – 2:30pmUlrike Bücking

Video

Title: Convergence results for discrete conformal maps based on conformally equivalent triangular lattices and circle patterns

Abstract: 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.
2:45 – 3:45pmNadav Dym

Video

Title: Computational theory of graphs, sets and rigid sets

Abstract: 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.
4:00 – 5:00pmProblems and applications discussion

Learn more about the Project on Geometric and Topological Methods for Analyzing Shapes

The 2022 NSF FRG workshop will take place at Harvard University on May 6-8, 2022.

Related Posts