Loading Events

« All Events

  • This event has passed.

2022 NSF FRG Workshop on Discrete Shapes

May 6, 2022 @ 10:00 am - May 8, 2022 @ 5:00 pm

On May 6–8, 2022, the CMSA  hosted a second NSF FRG Workshop.

This project brings together a community of researchers who develop theoretical and computational models to characterize shapes. Their combined interests span Mathematics (Geometry and Topology), Computer Science (Scientific Computing and Complexity Theory), and domain sciences, from Data Sciences to Computational Biology.

Scientific research benefits from the development of an ever-growing number of sensors that are able to capture details of the world at increasingly fine resolutions. The seemingly unlimited breadth and depth of these sources provide the means to study complex systems in a more comprehensive way. At the same time, however, these sensors are generating a huge amount of data that comes with a high level of complexity and heterogeneity, providing indirect measurements of hidden processes that provide keys to the systems under study. This has led to new challenges and opportunities in data analysis. Our focus is on image data and the shapes they represent. Advances in geometry and topology have led to powerful new tools that can be applied to geometric methods for representing, searching, simulating, analyzing, and comparing shapes. These methods and tools can be applied in a wide range of fields, including computer vision, biological imaging, brain mapping, target recognition, and satellite image analysis.

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

The workshop was held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA.

Workshop on Discrete Shapes
May 6–8, 2022


  • David Glickenstein (University of Arizona)
  • Joel Hass (University of California, Davis)
  • Patrice Koehl (University of California, Davis)
  • Feng Luo (Rutgers University, New Brunswick)
  • Maria Trnkova (University of California, Davis)
  • Shing-Tung Yau (Harvard)


  • Miri Ben-Chen (Technion)
  • Alexander Bobenko (TU Berlin)
  • John Bowers (James Madison)
  • Steven Gortler (Harvard)
  • David Gu (Stony Brook)
  • Anil Hirani (UIUC)
  • Yanwen Luo (Rutgers)
  • Peter Schroeder (Caltech)
  • Justin Solomon (MIT)
  • Tianqi Wu (Clark University)

Contributed Talk Speakers:

  • Oded Stein (MIT)
  • Bohan Zhou (Dartmouth)

Schedule (PDF)

Friday, May 6, 2022

10:00–10:05 am Welcome Opening
10:05–10:55 am Anil N. Hirani Title: Discrete vector bundles with connection

Abstract: We have recently initiated a generalization of discrete exterior calculus to differential forms with values in a vector bundle. A discrete vector bundle with connection over a simplicial complex has fibers at vertices and transport maps on edges, just as in lattice gauge theory. The first part of this work involves defining and examining properties of a combinatorial exterior covariant derivative and wedge product. We find that these operators commute with pullback under simplicial maps of the base space. From these definitions emerges a combinatorial curvature. In the second part of this work we showed that the curvature behaves as one expects: it measures failure of parallel transport to be independent of the path, and is the local obstruction to a trivialization. For a bundle with metric, metric compatibility of the discrete connection is equivalent to a Leibniz rule.  Vanishing curvature is indeed equivalent to an appropriately defined discrete flat connection, and curvature obstructs trivializability. In this talk I will focus on just the first part, and talk about naturality of the discrete exterior covariant derivative and discrete wedge product using simple examples. Joint work with Daniel Berwick-Evans (UIUC) and Mark Schubel (Apple, Inc.).

11:10–12:00 pm David Gu Title: Surface Quadrilateral Meshing Based on Abel-Jacobi Theory

Abstract: Surface quadrilateral meshing plays an important role in many fields. For example, in CAD (computer-aided design), all shapes are represented as Spline surfaces, which requires structured quad-meshing; in CAE (computer-aided engineering), the surface tessellation greatly affects the accuracy and efficiency of numerical simulations. Although the research on mesh generation has a long history, it remains a great challenge to automatically generate structured quad-meshes with high qualities. The key is to find the governing equation for the singularities of the global structured quad-meshes.

In this talk, we introduce our recent discovery:  the singularities of a quad-mesh are governed by the Abel theorem. We show that each quad-mesh determines a conformal structure and a meromorphic quadratic differential, the configuration of the mesh singularities can be described as the divisor of the differential. The quad-mesh divisor minus four times of the divisor of a holomorphic one-form is principal and satisfies the Abel theorem: its image under the Jacobi map is zero in the Jacobi variety.

This leads to a rigorous and efficient algorithm for surface structured quadrilateral meshing. After determining the singularities, the metric induced by the quad-mesh can be computed using the discrete Yambe flow, and the meromorphic quartic differential can be constructed, the trajectories of the differentials give the quad-mesh. The method can be applied directly for geometric modeling and computational mechanics.

12:00–2:00 pm Lunch Break
2:00–2:50 pm  Justin Solomon Title:  Geometry Processing with Volumes

Abstract:  Many algorithms in geometry processing are restricted to two-dimensional surfaces represented as triangle meshes.  Drawing inspiration from simulation, medical imaging, and other application domains, however, there is a substantial demand for geometry processing algorithms targeted to volumes represented as tetrahedral meshes or grids.  In this talk, I will summarize some efforts in our group to develop a geometry processing toolkit specifically for volumes.  Specifically, I will cover our recent work on hexahedral remeshing via cuboid decomposition, volumetric correspondence, and minimal surface computation via geometric measure theory.

3:00–3:20 pm Oded Stein Title: Optimization for flip-free parametrization

Abstract: Parametrizations without flipped elements are desirable in a variety of applications such as UV mapping and surface/volume correspondence. Computing flip-free parametrizations can be challenging, and there are many different approaches to the problem. In this talk we will look at multiple strategies for flip-free parametrizations that are based on the optimization of continuous energies. Due to the nature of the problem, these energies are often nonconvex and unbounded, which is a challenge for optimization methods. We will also take a closer look at our recently developed method for computing flip-free parametrizations using the Alternating Direction Method of Multipliers (ADMM).

3:20–4:00 pm Break
4:00–4:50 pm John Bowers Title: Koebe-Andre’ev-Thurston Packings via Flow

Abstract: Recently, Connelly and Gortler gave a novel proof of the circle packing theorem for tangency packings by introducing a hybrid combinatorial-geometric operation, flip-and-flow, that allows two tangency packings whose contact graphs differ by a combinatorial edge flip to be continuously deformed from one to the other while maintaining tangencies across all of their common edges. Starting from a canonical tangency circle packing with the desired number of circles a finite sequence of flip-and-flow operations may be applied to obtain a circle packing for any desired (proper) contact graph with the same number of circles.

The full Koebe-Andre’ev-Thurston theorem generalizes the circle packing theorem to allow for neighboring circles to overlap by angles up to $\pi/2$. In this talk I will show that the Connelly-Gortler method can be extended to allow for circles to overlap to angles up to $\pi/2$. This results in a new proof of the general Koebe-Andre’ev-Thurston theorem for disk patterns on $\mathbb{S}^2$ as well as a numerical algorithm for computing them. The proof involves generalizing a notion of convexity for circle polyhedra that was recently used to prove the global rigidity of certain circle packings, which is then used to show that all convex circle polyhedra are infinitesimally rigid, a result of independent interest.

5:00–5:30 pm Movies  “conform!” & ”Koebe polyhedra”


Saturday, May 7, 2022

9:30–10:20 am Alexander Bobenko Title: The Bonnet problem: Is a surface characterized by its metric and curvatures?

Abstract: We consider a classical problem in differential geometry, known as the Bonnet problem, whether a surface is characterized by a metric and mean curvature function. Generically, the answer is yes. Special cases when it is not the case are classified. In particular, we explicitly construct a pair of immersed tori that are related by a mean curvature preserving isometry. This resolves a longstanding open problem on whether the metric and mean curvature function determine a unique compact surface. Discrete differential geometry is used to find crucial geometric properties of surfaces. This is a joint work with Tim Hoffmann and Andrew Sageman-Furnas

10:20–11:00 am Break
11:00–11:50 am Miri Ben Chen Title: Surface Multigrid via Intrinsic Prolongation

Abstract: The solution of a linear system is a required ingredient in many geometry processing applications, and multigrid methods are among the most efficient solution techniques. However, due to the unstructured nature of triangle meshes, mapping functions between different multigrid levels is challenging. In this talk I will present our recent work that uses an intrinsic prolongation operator as the main building block in a multigrid solver for curved triangle meshes. Our solver can be used as a black-box in any triangle-mesh based system that requires a linear solve, and leads to order of magnitude time-efficiency improvement compared to direct solvers.

12:00–2:00 pm Lunch Break
2:00–2:50 pm Steven Gortler Title: Reconstructing configurations and graphs from unlabeled distance measurements

Abstract: Place a configuration of n  points (vertices) generically in R^d. Measure the Euclidean lengths of m point-pairs (edges). When is the underlying graph determined by these $m$ numbers (up to isomorphism)? When is the point configuration determined by these $m$ numbers (up to congruence)? This question is motivated by a number of inverse problem applications. In this talk, I will review what is known about this question.

3:00–3:20 pm Bohan Zhou Title: Efficient and Exact Multimarginal Optimal Transport with Pairwise Costs

Abstract: Optimal transport has profound and wide applications since its introduction in 1781 by Monge. Thanks to the Benamou-Brenier formulation, it provides a meaningful functional in the image science like image and shape registrations. However, exact computation through LP or PDE is in general not practical in large scale, while the popular entropy-regularized method introduces additional diffusion noise, deteriorating shapes and boundaries. Until the recent work [Jacobs and Leger, A Fast Approach to Optimal Transport: the back-and-forth method, Numerische Mathematik, 2020], solving OT in a both accurate and fast fashion finally becomes possible. Multiple marginal optimal transport is a natural extension from OT but has its own interest and is in general more computationally expensive. The entropy method suffers from both diffusion noise and high dimensional computational issues. In this work with Matthew Parno, we extend from two marginals to multiple marginals, on a wide class of cost functions when those marginals have a graph structure. This new method is fast and does not introduce diffusion. As a result, the new proposed method can be used in many fields those require sharp boundaries. If time allows, we will illustrate by examples the faithful joint recover via MMOT of images with sharp boundaries, with applications on sea ice prediction.

3:20–4:00 pm Break
4:00–4:50 pm Peter Schroeder Title: Constrained Willmore Surfaces

Abstract: The Willmore energy of a surface is a canonical example of a squared curvature bending energy. Its minimizers are therefore of interest both in the theory of surfaces and in practical applications from physical and geometric modeling. Minimizing the bending energy alone however is insufficient. Taking a cue from univariate splines which incorporate an isometry constraint we consider Willmore minimizers subject to a conformality constraint. In this talk I will report on a numerical algorithm to find such constrained minimizers for triangle meshes.

Joint work with Yousuf Soliman (Caltech), Olga Diamanti (UGraz), Albert Chern (UCSD), Felix Knöppel (TU Berlin), Ulrich Pinkall (TU Berlin).

5:00–5:50 pm Problems and Application discussions


Sunday, May 8, 2022

9:00–9:50 am Tianqi Wu Title: Convergence of discrete uniformizations

Abstract: The theory of discrete conformality, based on the notion of vertex scaling, has been implemented in computing conformal maps or uniformizations of surfaces. We will show that if a Delaunay triangle mesh approximates a smooth surface, then the related discrete uniformization will converge to the smooth uniformization, with an error bounded linearly by the size of the triangles in the mesh.

10:10–11:00 am Yanwen Luo Title:  Recent Progress in Spaces of Geodesic Triangulations of Surfaces

Spaces of geodesic triangulations of surfaces are natural discretization of the groups of surface diffeomorphisms isotopy to the identity. It has been conjectured that these spaces have the same homotopy type as their smooth counterparts. In this talk, we will report the recent progress in this problem. The key ingredient is the idea in Tutte’s embedding theorem. We will explain how to use it to identify the homotopy types of spaces of geodesic triangulations. This is joint work with Tianqi Wu and Xiaoping Zhu.
11:10–12:00 pm Problems and Application discussions
12:00–1:00 pm Movie “The Discrete Charm of Geometry”


May 6, 2022 @ 10:00 am
May 8, 2022 @ 5:00 pm
Event Categories:


20 Garden Street
Cambridge, MA 02138 United States
+ Google Map