CoBarS: Fast Reweighted Sampling for Polygon Spaces in Any Dimension
Jason Cantarella, Henrik Schumacher (2024)
Abstract. We present the first algorithm for sampling random configurations of closed \(n\)-gons with any fixed edgelengths \(r\_1, \dots, r\_n\) in any dimension \(d\) which is proved to sample correctly from standard probability measures on these spaces. We generate open \(n\)-gons as weighted sets of edge vectors on the unit sphere and close them by taking a Möbius transformation of the sphere which moves the center of mass of the edges to the origin. Using previous results of the authors, such a Möbius transformation can be found in \(O(n)\) time. The resulting closed polygons are distributed according to a pushforward measure. The main contribution of the present paper is the explicit calculation of reweighting factors which transform this pushforward measure to any one of a family of standard measures on closed polygon space, including the symplectic volume for polygons in \({\mathbb{R}}^3\). For fixed dimension, these reweighting factors may be computed in \(O(n)\) time. Experimental results show that our algorithm is efficient and accurate in practice, and an open-source reference implementation is provided.

journal

Repulsive Shells
Josua Sassen, Henrik Schumacher, Martin Rumpf, Keenan Crane (2024)
This paper develops a shape space framework for collision-aware geometric modeling, where basic geometric operations automatically avoid inter-penetration. Shape spaces are a powerful tool for surface modeling, shape analysis, nonrigid motion planning, and animation, but past formulations permit nonphysical intersections. Our framework augments an existing shape space using a repulsive energy such that collision avoidance becomes a first-class property, encoded in the Riemannian metric itself. In turn, tasks like intersection-free shape interpolation or motion extrapolation amount to simply computing geodesic paths via standard numerical algorithms. To make optimization practical, we develop an adaptive collision penalty that prevents mesh self-intersection, and converges to a meaningful limit energy under refinement. The final algorithms apply to any category of shape, and do not require a dataset of examples, training, rigging, nor any other prior information. For instance, to interpolate between two shapes we need only a single pair of meshes with the same connectivity. We evaluate our method on a variety of challenging examples from modeling and animation.

journal

A faster direct sampling algorithm for equilateral closed polygons and the probability of knotting
Jason Cantarella, Henrik Schumacher, Clayton Shonkwiler (2024)
We present a faster direct sampling algorithm for random equilateral closed polygons in three-dimensional space. This method improves on the moment polytope sampling algorithm of Cantarella et al (2016 J. Phys. A: Math. Theor. 49 275202) and has (expected) time per sample quadratic in the number of edges in the polygon. We use our new sampling method and a new code for computing invariants based on the Alexander polynomial to investigate the probability of finding unknots among equilateral closed polygons.

journal

A speed preserving Hilbert gradient flow for generalized integral Menger curvature
Jan Knappmann, Henrik Schumacher, Daniel Steenebrügge, Heiko von der Mosel (2023)
We establish long-time existence for a projected Sobolev gradient flow of generalized integral Menger curvature in the Hilbert case and provide $C^{1,1}$-bounds in time for the solution that only depend on the initial curve. The self-avoidance property of integral Menger curvature guarantees that the knot class of the initial curve is preserved under the flow, and the projection ensures that each curve along the flow is parametrized with the same speed as the initial configuration. Finally, we describe how to simulate this flow numerically with substantially higher efficiency than in the corresponding numerical $L^2$ gradient descent or other optimization methods.

journal arxiv

Computing the Conformal Barycenter
Jason Cantarella, Henrik Schumacher (2022)
The conformal barycenter of a point cloud on the sphere at infinity of the Poincaré ball model of hyperbolic space is a hyperbolic analogue of the geometric median of a point cloud in Euclidean space. It was defined by Douady and Earle as part of a construction of a conformally natural way to extend homeomorphisms of the circle to homeomorphisms of the disk, and it plays a central role in Millson and Kapovich's model of the configuration space of cyclic linkages with fixed edge lengths. In this paper we consider the problem of computing the conformal barycenter. Abikoff and Ye have given an iterative algorithm for measures on $\mathbb{S}^1$ which is guaranteed to converge. We analyze Riemannian versions of Newton's method computed in the intrinsic geometry of the Poincare ball model. We give Newton--Kantorovich (NK) conditions under which we show that Newton's method with fixed step size is guaranteed to converge quadratically to the conformal barycenter for measures on any $\mathbb{S}^d$ (including infinite-dimensional spheres). For measures given by $n$ atoms on a finite-dimensional sphere which obey the NK conditions, we give an explicit linear bound on the computation time required to approximate the conformal barycenter to fixed error. We prove that our NK conditions hold for all but exponentially few $n$ atom measures. For all measures with a unique conformal barycenter we show that a regularized Newton's method with line search will always converge (eventually superlinearly) to the conformal barycenter. Though we do not have hard time bounds for this algorithm, experiments show that it is extremely efficient in practice and in particular much faster than the Abikoff--Ye iteration.

journal

Sobolev gradients for the {Möbius} energy
Philipp Reiter, Henrik Schumacher (2021)
Aiming to optimize the shape of closed embedded curves within prescribed isotopy classes, we use a gradient-based approach to approximate stationary points of the Möbius energy. The gradients are computed with respect to Sobolev inner products similar to the $W^{3/2,2}$-inner product. This leads to optimization methods that are significantly more efficient and robust than standard techniques based on $L^2$-gradients.

journal arxiv

Repulsive Curves
Chris Yu, Henrik Schumacher, Keenan Crane (2021)
Curves play a fundamental role across computer graphics, physical simulation, and mathematical visualization, yet most tools for curve design do nothing to prevent crossings or self-intersections. This article develops efficient algorithms for (self-)repulsion of plane and space curves that are well-suited to problems in computational design. Our starting point is the so-called tangent-point energy, which provides an infinite barrier to self-intersection. In contrast to local collision detection strategies used in, e.g., physical simulation, this energy considers interactions between all pairs of points, and is hence useful for global shape optimization: local minima tend to be aesthetically pleasing, physically valid, and nicely distributed in space. A reformulation of gradient descent based on a Sobolev-Slobodeckij inner product enables us to make rapid progress toward local minima---independent of curve resolution. We also develop a hierarchical multigrid scheme that significantly reduces the per-step cost of optimization. The energy is easily integrated with a variety of constraints and penalties (e.g., inextensibility, or obstacle avoidance), which we use for applications including curve packing, knot untangling, graph embedding, non-crossing spline interpolation, flow visualization, and robotic path planning.

journal arxiv

Repulsive Surfaces
Chris Yu, Caleb Brakensiek, Henrik Schumacher, Keenan Crane (2021)
Functionals that penalize bending or stretching of a surface play a key role in geometric and scientific computing, but to date have ignored a very basic requirement: in many situations, surfaces must not pass through themselves or each other. This paper develops a numerical framework for optimization of surface geometry while avoiding (self-)collision. The starting point is the tangent-point energy, which effectively pushes apart pairs of points that are close in space but distant along the surface. We develop a discretization of this energy for triangle meshes, and introduce a novel acceleration scheme based on a fractional Sobolev inner product. In contrast to similar schemes developed for curves, we avoid the complexity of building a multiresolution mesh hierarchy by decomposing our preconditioner into two ordinary Poisson equations, plus forward application of a fractional differential operator. We further accelerate this scheme via hierarchical approximation, and describe how to incorporate a variety of constraints (on area, volume, etc.). Finally, we explore how this machinery might be applied to problems in mathematical visualization, geometric modeling, and geometry processing.

journal arxiv

Variational Methods for Discrete Geometric Functionals
Henrik Schumacher, Max Wardetzky (2020)
While consistent discrete notions of curvatures and differential operators have been widely studied, the question of whether the resulting minimizers converge to their smooth counterparts still remains open for various geometric functionals. Building on tools from variational analysis, and in particular using the notion of Kuratowski convergence, we offer a general framework for treating convergence of minimizers of (discrete) geometric functionals. We show how to apply the resulting machinery to minimal surfaces and Euler elasticae.

journal

Variational convergence of discrete elasticae
Sebastian Scholtes, Henrik Schumacher, Max Wardetzky (2020)
We discuss a discretization of the Euler--Bernoulli bending energy and of Euler elasticae under clamped boundary conditions by polygonal lines. We show Hausdorff convergence of the set of almost minimizers of the discrete bending energy to the set of smooth Euler elasticae under mesh refinement in (i) the $W^{1,\infty}$-topology for piecewise-linear interpolation; and in (ii) the $W^{2,p}$-topology, $p \in [2,\infty [$, using a suitable smoothing operator to create $W^{2,p}$-curves from polygons.

journal arxiv

Maximal discrete sparsity in parabolic optimal control with measures
Evelyn Herberg, Michael Hinze, Henrik Schumacher (2019)
We consider variational discretization of a parabolic optimal control problem governed by space-time measure controls. For the state discretization we use a Petrov-Galerkin method employing piecewise constant states and piecewise linear and continuous test functions in time. For the space discretization we use piecewise linear and continuous functions. As a result the controls are composed of Dirac measures in space-time, centered at points on the discrete space-time grid. We prove that the optimal discrete states and controls converge strongly in $L^q$ and weakly-$*$ in $\mathcal{M}$, respectively, to their smooth counterparts, where $q \in (1,\min\{2,1+2/d\}]$ is the spatial dimension. Furthermore, we compare our approach to [Casas, Kunisch - Parabolic control problems in space-time measure spaces], where the corresponding control problem is discretized employing a discontinuous Galerkin method for the state discretization and where the discrete controls are piecewise constant in time and Dirac measures in space. Numerical experiments highlight the features of our discrete approach.

Elastic energy regularization for inverse obstacle scattering problems
J. Eckhardt, R. Hiptmair, T. Hohage, H. Schumacher, M. Wardetzky (2019)
This paper is motivated by inverse problems in which the boundary curve of a smooth bounded domain has to be reconstructed from indirect measurements. As a classical example we study acoustic inverse obstacle scattering problems for cylindrical sound-soft scatterers using far-field measurements of scattered time-harmonic waves. By introducing a shape manifold as a solution set we allow the reconstruction of general, not necessarily star-shaped, curves. The bending energy is used as a stabilizing term in Tikhonov regularization to gain independence of the parametrization. Moreover, we discuss how self-intersections can be avoided by penalization with the Möbius energy and prove the regularizing property of our approach as well as convergence rates under variational source conditions. In a second part of the paper a discrete setting is introduced, and we describe a numerical method for finding the minimizer of the Tikhonov functional on the shape-manifold. Numerical examples demonstrate that our method can reconstruct non-star-shaped obstacles.

journal arxiv

Variational convergence of discrete minimal surfaces
Henrik Schumacher, Max Wardetzky (2019)
Building on and extending tools from variational analysis and relying on certain a priori assumptions, we prove Kuratowski convergence of sets of simplicial area minimizers to minimizers of the smooth Douglas-Plateau problem under simplicial refinement. This convergence is with respect to a topology that is finer than the topology of uniform convergence of both positions and surface normals.

journal arxiv

Pseudogradient flows of geometric energies
Henrik Schumacher (2018)
For differentiable functions on Riemannian manifolds, the gradient vector field and its induced gradient flow are well-defined and well-understood concepts. Unfortunately, many nonquadratic, infinite-dimensional optimization problems cannot be formulated on Riemannian manifolds in a convenient way. We introduce a category of infinite-dimensional Banach manifolds that allows us to define a generalized gradient. Moreover, we show short-time existence of the induced flows and apply their discretizations to the numerical minimization of various geometric energies of immersed curves and surfaces.

journal

On $H^2$-gradient Flows for the Willmore Energy
Henrik Schumacher (2017)
We show that the concept of $H^2$-gradient flow for the Willmore energy and other functionals that depend at most quadratically on the second fundamental form is well-defined in the space of immersions of Sobolev class $W^{2,p}$ from a compact, $n$-dimensional manifold into Euclidean space, provided that $p \geq 2$ and $p>n$. We also discuss why this is not true for Sobolev class $H^2= W^{2,2}$. In the case of equality constraints, we provide sufficient conditions for the existence of the projected $H^2$-gradient flow and demonstrate its usability for optimization with several numerical examples.

arxiv

Repulsive Curves and Surfaces
Henrik Schumacher (2022)
We discuss some of our recent findings on the consistency error of polyehdral discretizations of tangent-point energies for curves and surfaces. Moreover, we outline how Barnes-Hut and fast multipole techniques can be used to devise more efficient discretization.

journal

Polyhedral discretizations of tangent-point energies
Henrik Schumacher (2021)
We discuss some of our recent findings on the consistency error of polyehdral discretizations of tangent-point energies for curves and surfaces. Moreover, we outline how Barnes-Hut and fast multipole techniques can be used to devise more efficient discretization.

journal

Sparse discretization of sparse control problems
Evelyn Herberg, Michael Hinze, Henrik Schumacher (2019)
We consider optimal control problems that inherit a sparsity structure, especially we look at problems governed by measure controls. Our goal is to achieve maximal sparsity on the discrete level. We use variational discretization of the control problems utilizing a Petrov-Galerkin approximation of the state, which induces controls that are composed of Dirac measures. In the parabolic case this allows us to achieve sparsity on the discrete level in space and time. Numerical experiments show the differences of this approach to a full discretization approach.

journal

Convergence of discrete elastica
Sebastian Scholtes, Henrik Schumacher, Max Wardetzky (2012)
Using techniques related to the notions of epigraph distance and Attouch-Wets-convergence, we show that under appropriate boundary conditions discrete elastica (i.e., polygonal curves of some fixed length that minimize a certain discrete bending energy) converge to smooth elastica (i.e., smooth curves of some given length that minimize smooth bending energy).

journal

Conformal Maps and $p$-Dirichlet Energies
Henrik Schumacher (2013)
Let $\varPhi \colon (M_1,g_1) \to (M_2,g_2)$ be a diffeomorphism between Riemannian manifolds and $\varPhi^\# \colon \mathcal D(M_2) \to \mathcal D(M_1)$ the induced pull-back operator. The main theorem of this work relates preservation of the $p$-Dirichlet energies $\varphi \mapsto \int_{M_i} \left|\mathrm{d} \varphi\right|^p \, \mathrm{d} \mu_i$ under $\varPhi^\#$ to isometric or conformal properties of $\varPhi$. More precisely: In case $p=n$, $\varPhi^\#$ preserves the $p$-Dirichlet energy if and only if $\varPhi$ is conformal. In case $n\neq p \geq 2$, energy preservation is equivalent to $\varPhi$ being an isometry.

Variational Convergence and Discrete Minimal Surfaces
Henrik Schumacher (2015)
This work is concerned with the convergence behavior of the solutions to parametric variational problems. An emphasis is put on sequences of variational problems that arise as discretizations of either infinite-dimensional optimization problems or infinite-dimensional operator problems. Finally, the results are applied to discretizations of the Douglas-Plateau problem and of a boundary value problem in nonlinear elasticity.

Generalized Seiberg--Witten equations: Swann bundles and $L^\infty$-estimates
Henrik Schumacher (2010)
In this diploma thesis, a non-linear Dirac operator and generalized Seiberg-Witten equations for 4-manifolds are studied. By using its relations to hyperKähler geometry, a pointwise Lichnerowicz formula for the non-linear Dirac operator is derived. This is used to obtain an a priori $L^\infty$-estimate on the spinor part of solutions of the generalized Seiberg--Witten equations. Finally, some remarks towards compactification of moduli spaces are made.