An official website of the United States government
Abstract When an overhand knot tied in an elastic rod is tightened, it can undergo a sudden change in shape through snap buckling. In this article, we use a combination of discrete differential geometry (DDG)-based simulations and tabletop experiments to explore the onset of buckling as a function of knot topology, rod geometry, and friction. In our setup, two open ends of an overhand knot are slowly pulled apart, which leads to snap buckling in the knot loop. We call this phenomenon “inversion” since the loop appears to move dramatically from one side of the knot to the other. This inversion occurs due to the coupling of elastic energy between the braid (the portion of the knot in self-contact) and the loop (the portion of the knot with two ends connected to the braid). A numerical framework is implemented that combines discrete elastic rods with a constraint-based method for frictional contact to explore inversion in overhand knots. The numerical simulation robustly captures inversion in the knot and is found to be in good agreement with experimental results. In order to gain physical insight into the inversion process, we also develop a simplified model of the knot that does not require simulation of self-contact, which allows us to visualize the bifurcation that results in snap buckling.
more »
« less
A Glimpse into Discrete Differential Geometry
The emerging field of discrete differential geometry (DDG) studies discrete analogues of smooth geometric objects, providing an essential link between analytical descriptions and computation. In recent years it has unearthed a rich variety of new perspectives on applied problems in computational anatomy/biology, computational mechanics, industrial design, computational architecture, and digital geometry processing at large. The basic philosophy of discrete differential geometry is that a discrete object like a polyhedron is not merely an approximation of a smooth one, but rather a differential geometric object in its own right. In contrast to traditional numerical analysis which focuses on eliminating approximation error in the limit of refinement (e.g., by taking smaller and smaller finite differences), DDG places an emphasis on the so-called “mimetic” viewpoint, where key properties of a system are preserved exactly, independent of how large or small the elements of a mesh might be. Just as algorithms for simulating mechanical systems might seek to exactly preserve physical invariants such as total energy or momentum, structure-preserving models of discrete geometry seek to exactly preserve global geometric invariants such as total curvature. More broadly, DDG focuses on the discretization of objects that do not naturally fall under the umbrella of traditional numerical analysis. This article provides an overview of some of the themes in DDG.
more »
« less
- Award ID(s):
- 1717320
- PAR ID:
- 10060772
- Date Published:
- Journal Name:
- Notices of the American Mathematical Society
- Volume:
- 64
- Issue:
- 10
- ISSN:
- 1088-9477
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Curvature is a fundamental geometric characteristic of smooth spaces. In recent years different notions of curvature have been developed for combinatorial discrete objects such as graphs. However, the connections between such discrete notions of curvature and their smooth counterparts remain lurking and moot. In particular, it is not rigorously known if any notion of graph curvature converges to any traditional notion of curvature of smooth space. Here we prove that in proper settings the Ollivier–Ricci curvature of random geometric graphs in Riemannian manifolds converges to the Ricci curvature of the manifold. This is the first rigorous result linking curvature of random graphs to curvature of smooth spaces. Our results hold for different notions of graph distances, including the rescaled shortest path distance, and for different graph densities. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear.more » « less
-
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 thetangent-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.more » « less
-
Kernel methods for solving partial differential equations work coordinate-free on the surface and yield high approximation rates for smooth solutions. Localized Lagrange bases have proven to alleviate the computational complexity of usual kernel methods for data fitting problems, but the efficient numerical solution of the ill-conditioned linear systems of equations arising from kernel- based Galerkin solutions to PDEs is a challenging problem which has not been addressed in the literature so far. In this article we apply the framework of the geometric multigrid method with a τ ≥ 2-cycle to scattered, quasi-uniform point clouds on the surface. We show that the resulting solver can be accelerated by using the Lagrange function decay and obtain satisfying convergence rates by a rigorous analysis. In particular, we show that the computational cost of the linear solver scales log-linear in the degrees of freedom.more » « less
-
Intersection graphs of planar geometric objects such as intervals, disks, rectangles and pseudodisks are well-studied. Motivated by various applications, Butman et al. (ACM Trans. Algorithms, 2010) considered algorithmic questions in intersection graphs of $$t$$-intervals. A $$t$$-interval is a union of $$t$$ intervals --- these graphs are also referred to as multiple-interval graphs. Subsequent work by Kammer et al.\ (APPROX-RANDOM 2010) considered intersection graphs of $$t$$-disks (union of $$t$$ disks), and other geometric objects. In this paper we revisit some of these algorithmic questions via more recent developments in computational geometry. For the \emph{minimum-weight dominating set problem} in $$t$$-interval graphs, we obtain a polynomial-time $$O(t \log t)$$-approximation algorithm, improving upon the previously known polynomial-time $t^2$-approximation by Butman et al. In the same class of graphs we show that it is $$\NP$$-hard to obtain a $$(t-1-\epsilon)$$-approximation for any fixed $$t \ge 3$$ and $$\epsilon > 0$$. The approximation ratio for dominating set extends to the intersection graphs of a collection of $$t$$-pseudodisks (nicely intersecting $$t$$-tuples of closed Jordan domains). We obtain an $$\Omega(1/t)$$-approximation for the \emph{maximum-weight independent set} in the intersection graph of $$t$$-pseudodisks in polynomial time. Our results are obtained via simple reductions to existing algorithms by appropriately bounding the union complexity of the objects under consideration.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
