Curve-shortening flow
In mathematics, the curve-shortening flow is a process that modifies a smooth curve in the Euclidean plane by moving its points perpendicularly to the curve at a speed proportional to the curvature. The curve-shortening flow is an example of a geometric flow, and is the one-dimensional case of the mean curvature flow. Other names for the same process include the Euclidean shortening flow, geometric heat flow, and arc length evolution.
As the points of any smooth simple closed curve move in this way, the curve remains simple and smooth. It loses area at a constant rate, and its perimeter decreases as quickly as possible for any continuous curve evolution. If the curve is non-convex, its total absolute curvature decreases monotonically, until it becomes convex. Once convex, the isoperimetric ratio of the curve decreases as the curve converges to a circular shape, before collapsing to a single point of singularity. If two disjoint simple smooth closed curves evolve, they remain disjoint until one of them collapses to a point.
The circle is the only simple closed curve that maintains its shape under the curve-shortening flow, but some curves that cross themselves or have infinite length keep their shape, including the grim reaper curve, an infinite curve that translates upwards, and spirals that rotate while remaining the same size and shape.
An approximation to the curve-shortening flow can be computed numerically, by approximating the curve as a polygon and using the finite difference method to calculate the motion of each polygon vertex. Alternative methods include computing a convolution of polygon vertices and then resampling vertices on the resulting curve, or repeatedly applying a median filter to a digital image whose black and white pixels represent the inside and outside of the curve.
The curve-shortening flow was originally studied as a model for annealing of metal sheets. Later, it was applied in image analysis to give a multi-scale representation of shapes. It can also model reaction–diffusion systems, and the behavior of cellular automata. In pure mathematics, the curve-shortening flow can be used to find closed geodesics on Riemannian manifolds, and as a model for the behavior of higher-dimensional flows.
Definitions
A flow is a process in which the points of a mathematical space continuously change their locations or properties over time. More specifically, in a one-dimensional geometric flow such as the curve-shortening flow, the points undergoing the flow belong to a curve, and what changes is the shape of the curve, its embedding into the Euclidean plane determined by the locations of each of its points.In the curve-shortening flow, each point of a curve moves in the direction of a normal vector to the curve, at a rate proportional to the curvature. For an evolving curve represented by a two-parameter function where parameterizes the arc length along the curve and parameterizes a time in the evolution of the curve, the curve-shortening flow can be described by the parabolic partial differential equation
a form of the heat equation, where is the curvature and is the unit normal vector.
Because the ingredients of this equation, the arc length, curvature, and time, are all unaffected by translations and rotations of the Euclidean plane, it follows that the flow defined by this equation is invariant under translations and rotations. If the plane is scaled by a constant dilation factor, the flow remains essentially unchanged, but is slowed down or sped up by the same factor.
Non-smooth curves
In order for the flow to be well defined, the given curve must be sufficiently smooth that it has a continuous curvature. However, once the flow starts, the curve becomes analytic, and remains so until reaching a singularity at which the curvature blows up. For a smooth curve without crossings, the only possible singularity happens when the curve collapses to a point, but immersed curves can have other types of singularity.In such cases, with some care it is possible to continue the flow past these singularities until the whole curve shrinks to a single point.
For a simple closed curve, using an extension of the flow to non-smooth curves based on the level-set method, there are only two possibilities. Curves with zero Lebesgue measure instantly evolve into smooth curves, after which they evolve as any smooth curve would. However, Osgood curves with nonzero measure instead immediately evolve into a topological annulus with nonzero area and smooth boundaries. The topologist's sine curve is an example that instantly becomes smooth, despite not even being locally connected; examples such as this show that the reverse evolution of the curve-shortening flow can take well-behaved curves to complicated singularities in a finite amount of time.
Non-Euclidean surfaces
The curve-shortening flow, and many of the results about the curve-shortening flow, can be generalized from the Euclidean plane to any two-dimensional Riemannian manifold. In order to avoid additional types of singularity, it is important for the manifold to be convex at infinity; this is defined to mean that every compact set has a compact convex hull, as defined using geodesic convexity. The curve-shortening flow cannot cause a curve to depart from its convex hull, so this condition prevents parts of the curve from reaching the boundary of the manifold.Space curves
The curve-shortening flow has also been studied for curves in three-dimensional Euclidean space. The normal vector in this case can be defined as the derivative of the tangent vector with respect to arc length, normalized to be a unit vector; it is one of the components of the Frenet–Serret frame. It is not well defined at points of zero curvature, but the product of the curvature and the normal vector remains well defined at those points, allowing the curve-shortening flow to be defined. Curves in space may cross each other or themselves according to this flow, and the flow may lead to singularities in the curves; every singularity is asymptotic to a plane. The curve shortening flow for space curves has been used as a way to define flow past singularities in plane curves.Beyond curves
It is possible to extend the definition of the flow to more general inputs than curves, for instance by using rectifiable varifolds or the level-set method. However, these extended definitions may allow parts of curves to vanish instantaneously or fatten into sets of nonzero area.A commonly studied variation of the problem involves networks of interior-disjoint smooth curves, with junctions where three or more of the curves meet. When the junctions all have exactly three curves meeting at angles of 2/3 the flow is well-defined for the short term. However, it may eventually reach a singular state with four or more curves meeting at a junction, and there may be more than one way to continue the flow past such a singularity.
Behavior
Avoidance principle, radius, and stretch factor
If two disjoint smooth simple closed curves undergo the curve-shortening flow simultaneously, they remain disjoint as the flow progresses. The reason is that, if two smooth curves move in a way that creates a crossing, then at the time of first crossing the curves would necessarily be tangent to each other, without crossing. But, in such a situation, the two curves' curvatures at the point of tangency would necessarily pull them apart rather than pushing them together into a crossing. For the same reason, a single simple closed curve can never evolve to cross itself. This phenomenon is known as the avoidance principle.The avoidance principle implies that any smooth curve eventually either reaches a singularity or collapses to a point. For, if a given smooth curve is surrounded by a circle, both will remain disjoint until one or the other collapses or reaches a singularity. But the enclosing circle shrinks under the curvature flow, remaining circular, until it collapses, and by the avoidance principle must remain contained within it. By the same reasoning, the radius of the smallest circle that encloses must decrease at a rate that is at least as fast as the decrease in radius of a circle undergoing the same flow.
quantifies the avoidance principle for a single curve in terms of the ratio between the arc length and Euclidean distance between pairs of points, sometimes called the stretch factor. He shows that the stretch factor is strictly decreasing at each of its local maxima, except for the case of the two ends of a diameter of a circle in which case the stretch factor is constant at. This monotonicity property implies the avoidance principle, for if the curve would ever touch itself the stretch factor would become infinite at the two touching points.
Length
As a curve undergoes the curve-shortening flow, its length decreases at a rate given by the formulawhere the interval is taken over the curve, is the curvature, and is arc length along the curve.
The integrand is always non-negative, and for any smooth closed curve there exist arcs within which it is strictly positive, so the length decreases monotonically.
More generally, for any evolution of curves whose normal speed is,
the rate of change in length is
which can be interpreted as a negated inner product between the given evolution and the curve-shortening flow.
Thus, the curve-shortening flow can be described as the gradient flow for length, the flow that decreases the length of the curve as quickly as possible relative to the norm of the flow. This property is the one that gives the curve-shortening flow its name.
Area
For a simple closed curve, the area enclosed by the curve shrinks, at the constant rate of 2 units of area per unit of time, independent of the curve. Therefore, the total time for a curve to shrink to a point is proportional to its area, regardless of its initial shape.Because the area of a curve is reduced at a constant rate, and a circle has the greatest possible area among simple closed curves of a given length, it follows that circles are the slowest curves to collapse to a point under the curve-shortening flow. All other curves take less time to collapse than a circle of the same length.
The constant rate of area reduction is the only conservation law satisfied by the curve-shortening flow. This implies that it is not possible to express the "vanishing point" where the curve eventually collapses as an integral over the curve of any function of its points and their derivatives, because such an expression would lead to a forbidden second conservation law. However, by combining the constant rate of area loss with the avoidance principle, it is possible to prove that the vanishing point always lies within a circle, concentric with the minimum enclosing circle, whose area is the difference in areas between the enclosing circle and the given curve.
Total absolute curvature
The total absolute curvature of a smooth curve is the integral of the absolute value of the curvature along the arc length of the curve,It can also be expressed as a sum of the angles between the normal vectors at consecutive pairs of inflection points. It is 2 for convex curves and larger for non-convex curves, serving as a measure of non-convexity of a curve.
New inflection points cannot be created by the curve-shortening flow.
Each of the angles in the representation of the total absolute curvature as a sum decreases monotonically, except at the instants when two consecutive inflection points reach the same angle or position as each other and are both eliminated.
Therefore, the total absolute curvature can never increase as the curve evolves. For convex curves it is constant at 2 and for non-convex curves it decreases monotonically.
Gage–Hamilton–Grayson theorem
If a smooth simple closed curve undergoes the curve-shortening flow, it remains smoothly embedded without self-intersections. It will eventually become convex, and once it does so it will remain convex. After this time, all points of the curve will move inwards, and the shape of the curve will converge to a circle as the whole curve shrinks to a single point. This behavior is sometimes summarized by saying that every simple closed curve shrinks to a "round point".This result is due to Michael Gage, Richard S. Hamilton, and Matthew Grayson. proved convergence to a circle for convex curves that contract to a point. More specifically Gage showed that the isoperimetric ratio decreases monotonically and quickly. proved that all smooth convex curves eventually contract to a point without forming any other singularities, and proved that every non-convex curve will eventually become convex. provide a simpler proof of Grayson's result, based on the monotonicity of the stretch factor.
.
Similar results can be extended from closed curves to unbounded curves satisfying a local Lipschitz condition. For such curves, if both sides of the curve have infinite area, then the evolved curve remains smooth and singularity-free for all time. However, if one side of an unbounded curve has finite area, and the curve has finite total absolute curvature, then its evolution reaches a singularity in time proportional to the area on the finite-area side of the curve, with unbounded curvature near the singularity. For curves that are graphs of sufficiently well-behaved functions, asymptotic to a ray in each direction, the solution converges in shape to a unique shape that is asymptotic to the same rays.
For networks formed by two disjoint rays on the same line, together with two smooth curves connecting the endpoints of the two rays, an analogue of the Gage–Hamilton–Grayson theorem holds, under which the region between the two curves becomes convex and then converges to a vesica piscis shape.
Singularities of self-crossing curves
Curves that have self-crossings may reach singularities before contracting to a point. For instance, if a lemniscate has unequal areas in its two lobes, then eventually the smaller lobe will collapse to a point. However, if the two lobes have equal areas, then they will remain equal throughout the evolution of the curve, and the isoperimetric ratio will diverge as the curve collapses to a singularity.When a locally convex self-crossing curve approaches a singularity as one of its loops shrinks, it either shrinks in a self-similar way or asymptotically approaches the grim reaper curve as it shrinks. When a loop collapses to a singularity, the amount of total absolute curvature that is lost is either at least 2 or exactly.
On Riemannian manifolds
On a Riemannian manifold, any smooth simple closed curve will remain smooth and simple as it evolves, just as in the Euclidean case. It will either collapse to a point in a finite amount of time, or remain smooth and simple forever. In the latter case, the curve necessarily converges to a closed geodesic of the surface.Immersed curves on Riemannian manifolds, with finitely many self-crossings, become self-tangent only at a discrete set of times, at each of which they lose a crossing. As a consequence the number of self-crossing points is non-increasing.
Curve shortening on a sphere can be used as part of a proof of the tennis ball theorem. This theorem states that every smooth simple closed curve on the sphere that divides the sphere's surface into two equal areas must have at least four inflection points. The proof comes from the observation that curve shortening preserves the smoothness and area-bisection properties of the curve, and does not increase its number of inflection points. Therefore, it allows the problem to be reduced to the problem for curves near the limiting shape of curve shortening, a great circle.
Huisken's monotonicity formula
According to Huisken's monotonicity formula, the convolution of an evolving curve with a time-reversed heat kernel is non-increasing. This result can be used to analyze the singularities of the evolution.Specific curves
Curves with self-similar evolution
Because every other simple closed curve converges to a circle, the circle is the only simple closed curve that keeps its shape under the curve-shortening flow. However, there are many other examples of curves that are either non-simple or non-closed and keep their shape. In particular,- Every line stays unchanged by the curve-shortening flow. Lines are the only curves that are unaffected by the curve-shortening flow, although there exist more complex stable networks of curves, such as the hexagonal tiling of the plane.
- The grim reaper curve moves upwards without changing its shape. In the same way, any curve similar to the grim reaper is translated by the curve-shortening flow, shifted in the direction of the symmetry axis of the curve without changing its shape or orientation. The grim reaper is the only curve with this property. It is also called the hairpin model in the physics literature.
- A family of self-crossing closed curves, derived from projections of torus knots, shrink homothetically but remain self-similar under the curve-shortening flow. These have come to be known as the Abresch–Langer curves, after the work of, although they were mentioned earlier by and rediscovered independently by. These curves are locally convex, and therefore can be described by their support functions. Suitably scaled versions of these support functions obey the differential equation
- :
- Other curves, including some infinite spirals, remain self-similar with more complicated motions including rotation or combinations of rotation, shrinking or expansion, and translation.
- For networks of smooth curves, meeting in threes at junctions with angles of 2/3, the self-similar shrinking solutions include a double bubble surrounding two equal areas, a lens shape bounded by two congruent arcs of circles together with two collinear rays having their apexes at the corners of the lens, and a "fish-shaped" network bounded by a line segment, two rays, and a convex curve. Any other self-similar shrinking networks involve a larger number of curves. Another family of networks grows homothetically and remains self-similar; these are tree-like networks of curves, meeting at angles of 2/3 at triple junctions, asymptotic to a fan of two or more rays that meet at a common endpoint. The two-ray case of these shapes is an unbounded smooth curve; for three or more rays the evolution of these shapes may be defined using generalized variants of the curve-shortening flow such as the one for varifolds. A given fan of four or more rays may be asymptotic to more than one different solution of this type, so these solutions do not provide a unique definition for the curve-shortening flow starting from a fan of rays.
Ancient solutions
The only closed curves other than the circle and Abresch–Langer curves that form ancient solutions are a class of curves called the Angenent ovals after the work of. These curves may be parameterized by specifying their curvature as a function of the tangent angle using the formula
and have as their limiting shape under reverse evolution a pair of grim reaper curves approaching each other from opposite directions.
In the Cartesian coordinate system, they may be given by the implicit curve equation
In the physics literature, the same shapes are known as the paperclip model.
For more general classes of curves, such as the graphs of functions,
a more diverse collection of ancient solutions is known.
Numerical approximations
In order to compute the curve-shortening flow efficiently, both a continuous curve and the continuous evolution of the curve need to be replaced by a discrete approximation.Front tracking
methods have long been used in fluid dynamics to model and track the motion of boundaries between different materials, of steep gradients in material properties such as weather fronts, or of shock waves within a single material. These methods involve deriving the equations of motion of the boundary, and using them to directly simulate the motion of the boundary, rather than simulating the underlying fluid and treating the boundary as an emergent property of the fluid. The same methods can also be used to simulate the curve-shortening flow, even when the curve undergoing the flow is not a boundary or shock.In front tracking methods for curve shortening, the curve undergoing the evolution is discretized as a polygon. The finite difference method is used to derive formulas for the approximate normal vector and curvature at each vertex of the polygon, and these values are used to determine how to move each vertex in each time step. Although the curve-shortening flow is defined by the motion of a curve perpendicularly to itself, some parameterizations of the curve-shortening flow may allow the vertices that approximate the curve to move non-perpendicularly. In effect, this allows the vertices to move along the curve, as the curve evolves. Choosing a careful reparameterization can help redistribute the vertices more evenly along the curve in situations where perpendicular motion would cause them to bunch up. write that these methods are fast and accurate but that it is much more complicated to extend them to versions of the curve-shortening flow that apply to more complicated inputs than simple closed curves, where it is necessary to deal with singularities and changes of topology.
For most such methods, warns that "The conditions of stability cannot be determined easily and the time step must be chosen ad hoc." Another finite differencing method by modifies the formula for the curvature at each vertex by adding to it a small term based on the Laplace operator. This modification is called elliptic regularization, and it can be used to help prove the existence of generalized flows as well as in their numerical simulation. Using it, the method of Crandall and Lions can be proven to converge and is the only numerical method listed by Cao that is equipped with bounds on its convergence rate. For an empirical comparison of the forward Euler, backward Euler, and more accurate Crank–Nicolson finite difference methods, see.
Resampled convolution
suggest a numerical method for computing an approximation to the curve-shortening flow that maintains a discrete approximation to the curve and alternates between two steps:- Resample the current curve by placing new sample points at a uniform spacing, as measured by normalized arc length.
- Convolve the locations of the points with a Gaussian function with small standard deviation, in effect replacing each point's location with a weighted average of the locations of nearby points along the curve, with Gaussian weights. The standard deviation of the Gaussian should be chosen to be small enough that, after this step, the sample points still have nearly-uniform spacing.
Median filtering
describe a scheme operating on a two-dimensional square grid – effectively an array of pixels.The curve to be evolved is represented by assigning the value 0 to pixels exterior to the curve, and 1 to pixels interior to the curve, giving the indicator function for the interior of the curve. This representation is updated by alternating two steps:
- Convolve the pixelated image with a heat kernel to simulate its evolution under the heat equation for a short time step. The result is a Gaussian blur of the image, or equivalently the Weierstrass transform of the indicator function, with radius proportional to the square root of the time step.
- Set every pixel with numerical value less than 1/2 to 0, and every pixel with numerical value greater than 1/2 to 1, thresholding the image back to its original values in new positions.
The method can be generalized to the evolution of networks of curves, meeting at junctions and dividing the plane into more than three regions, by applying the same method simultaneously to each region.
Instead of blurring and thresholding, this method can alternatively be described as applying a median filter with Gaussian weights to each pixel. It is possible to use kernels other than the heat kernel, or to adaptively refine the grid so that it has high resolution near the curve but does not waste time and memory on pixels far from the curve that do not contribute to the outcome. Instead of using only the two values in the pixelated image, a version of this method that uses an image whose pixel values represent the signed distance to the curve can achieve subpixel accuracy and require lower resolution.
Applications
Annealing metal sheets
An early reference to the curve-shortening flow by motivates it as a model for the physical process of annealing, in which heat treatment causes the boundaries between grains of crystallized metal to shift. Unlike soap films, which are forced by differences in air pressure to become surfaces of constant mean curvature, the grain boundaries in annealing are subject only to local effects, which cause them to move according to the mean curvature flow. The one-dimensional case of this flow, the curve-shortening flow, corresponds to annealing sheets of metal that are thin enough for the grains to become effectively two-dimensional and their boundaries to become one-dimensional.Shape analysis
In image processing and computer vision, suggest applying the curve-shortening flow to the outline of a shape derived from a digital image, in order to remove noise from the shape and provide a scale space that provides a simplified description of the shape at different levels of resolution.The method of Mokhtarian and Mackworth involves computing the curve-shortening flow, tracking the inflection points of the curve as they progress through the flow, and drawing a graph that plots the positions of the inflection points around the curve against the time parameter. The inflection points will typically be removed from the curve in pairs as the curve becomes convex and the lifetime of a pair of points corresponds to the salience of a feature of the shape.
Because of the resampled convolution method that they describe for computing a numerical approximation of the curve-shortening flow, they call their method the resampled curvature scale space. They observe that this scale space is invariant under Euclidean transformations of the given shape, and assert that it uniquely determines the shape and is robust against small variations in the shape. They compare it experimentally against several related alternative definitions of a scale space for shapes, and find that the resampled curvature scale space is less computationally intensive, more robust against nonuniform noise, and less strongly influenced by small-scale shape differences.
Reaction–diffusion
In reaction–diffusion systems modeled by the Allen–Cahn equation, the limiting behavior for fast reaction, slow diffusion, and two or more local minima of energy with the same energy level as each other is for the system to settle into regions of different local minima, with the fronts delimiting boundaries between these regions evolving according to the curve-shortening flow.Cellular automata
In a cellular automaton, each cell in an infinite grid of cells may have one of a finite set of states, and all cells update their states simultaneously based only on the configuration of a small set of neighboring cells.A Life-like cellular automaton rule is one in which the grid is the infinite square lattice, there are exactly two cell states, the set of neighbors of each cell are the eight neighbors of the Moore neighborhood,
and the update rule depends only on the number of neighbors with each of the two states rather than on any more complicated function of those states.
In one particular life-like rule, introduced by Gerard Vichniac and called the twisted majority rule or annealing rule, the update rule sets the new value for each cell to be the majority among the nine cells given by it and its eight neighbors, except
when these cells are split among four with one state and five with the other state, in which case the new value of the cell is the minority rather than the majority.
The detailed dynamics of this rule are complicated, including the existence of small stable structures. However, in the aggregate it tends to form large regions of cells that are all in the same state as each other, with the boundaries between these regions evolving according to the curve-shortening flow.
Construction of closed geodesics
The curve-shortening flow can be used to prove an isoperimetric inequality for surfaces whose Gaussian curvature is a non-increasing function of the distance from the origin, such as the paraboloid. On such a surface, the smooth compact set that has any given area and minimum perimeter for that area is necessarily a circle centered at the origin. The proof applies the curve-shortening flow to two curves, a metric circle and the boundary of any other compact set, and compares the change in perimeter of the two curves as they are both reduced to a point by the flow.The curve-shortening flow can also be used to prove the theorem of the three geodesics, that every smooth Riemannian manifold topologically equivalent to a sphere has three geodesics that form simple closed curves.
Related flows
Other geometric flows related to the curve-shortening flow include the following ones.- For simulating the behavior of crystals or other anisotropic materials, it is important to have variants of the curve-shortening flow for which the speed of flow depends on the orientation of a curve as well as on its curvature. One way of doing this is to define the energy of a curve to be the integral of a smooth function of its normal vectors, and form the gradient flow of this energy, according to which the normal speed at which the curve flows is proportional to an anisotropic analog of the curvature. This flow can be simulated by discretizing the curve as a polygon. In numerical experiments, initial curves appear to converge to the Wulff shape for before shrinking to a point. Alternatively, one can let the curve flow with speed where is the curvature and and are smooth functions of the orientation. When and , the resulting flow can be shown to obey the avoidance principle and an analog of the Gage–Hamilton–Grayson theorem.
- The affine curve-shortening flow was first investigated by and. In this flow, the normal speed of the curve is proportional to the cube root of the curvature. The resulting flow is invariant under the affine transformations of the Euclidean plane, a larger symmetry group than the similarity transformations under which the curve-shortening flow is invariant. Under this flow, an analogue of the Gage–Hamilton–Grayson theorem applies, under which any simple closed curve eventually becomes convex and then converges to an ellipse as it collapses to a point.
- Transforming a curve with equal normal speeds at all points has been called the grassfire transform. Curves evolved in this way will in general develop sharp corners, the trace of which forms the medial axis of the curve. A closely related curve evolution which moves straight segments of a polygonal curve at equal speeds but allows concave corners to move more quickly than unit speed instead forms a different type of topological skeleton of the given curve, its straight skeleton.
- For surfaces in higher dimensions, there is more than one definition of curvature, including extrinsic measures such as the mean curvature and intrinsic measures such as the Gaussian curvature and Ricci curvature. Correspondingly, there are several ways of defining geometric flows based on curvature, including the mean curvature flow, the Ricci flow and the Willmore flow. The curve-shortening flow is a special case of the mean curvature flow for one-dimensional curves.
- Inspired by the curve-shortening flow on smooth curves, researchers have studied methods for flowing polygons so that they stay polygonal, with applications including pattern formation and synchronization in distributed systems of robots. Length-preserving polygonal flows can be used to solve the carpenter's rule problem.
- In computer vision, the active contour model for edge detection and image segmentation is based on curve shortening, and evolves curves based on a combination of their curvature and the features of an image.