Curve-shortening flow

A flow is a process in which the points of a 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 :\frac{\partial C}{\partial t} = \frac{\partial^2 C}{\partial s^2} = \kappa n, 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 (or more precisely, equivariant). 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 (including all polygons and piecewise-smooth curves) 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 in the plane) 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. However, spherical curves and curves which can be orthogonally projected into a regular convex planar curve are known to remain simple. 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 same conditions seen in an optimal Steiner tree or two-dimensional foam of soap bubbles) 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 closed curve must eventually reach a singularity, such as a point of infinite curvature. For, if a given smooth curve is surrounded by a circle, both will remain disjoint for as long as they both exist. But the enclosing circle shrinks under the curvature flow, remaining circular, until it collapses, and by the avoidance principle must remain contained within it. So, if were to never reach a singularity, it would be trapped at a single point at the time when the circle collapses, which is impossible for a smooth curve. This can be quantified by observing that 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 (of the shorter of two arcs) 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 formula :\frac{dL}{dt} = -\int \kappa^2 \, ds, where the integral 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 :\frac{dL}{dt} = -\int f\kappa \, ds, 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 (locally) 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 (by the isoperimetric inequality) 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, :K=\int|\kappa| \,ds. 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 (the ratio of squared curve length to area, a number that is 4 for a circle and larger for any other convex curve) 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. has the shape of a vesica piscis. 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 (any smooth immersed curve with a single crossing, resembling a figure 8 or infinity symbol) 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 (described below) 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 (like the seam of a tennis ball) 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 (they include self-crossings) or non-closed (they extend to infinity) 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, Ancient solutions An ancient solution to a flow problem is a curve whose evolution can be extrapolated backwards for all time, without singularities. All of the self-similar solutions that shrink or stay the same size rather than growing are ancient solutions in this sense; they can be extrapolated backwards by reversing the self-similarity transformation that they would undergo by the forwards curve-shortening flow. Thus, for instance, the circle, grim reaper, and Abresch–Langer curves are all ancient solutions. There are also examples which are not self-similar. An explicit example is the Angenent oval solution after the work of . This family of curves may be parameterized by specifying the curvature as a function of the tangent angle using the formula :k(\theta,t)=\sqrt{\cos 2\theta-\operatorname{coth} 2t} 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 :\cosh y - e^{-t}\cos x = 0. In the physics literature, the same shapes are known as the paperclip model. The Angenent oval and shrinking circle solutions are the only ancient solutions whose timeslices bound bounded convex sets. The Grim Reaper, stationary halfspace and stationary strip solutions are the only examples whose timeslices bound unbounded convex sets. There exist many further (nonembedded) locally convex examples as well as many further (nonconvex) embedded examples. ==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 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. As they show, this method converges to the curve-shortening distribution in the limit as the number of sample points grows and the normalized arc length of the convolution radius shrinks. 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 (black) to pixels exterior to the curve, and 1 (white) 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. In order for this scheme to be accurate, the time step must be large enough to cause the curve to move by at least one pixel even at points of low curvature, but small enough to cause the radius of blurring to be less than the minimum radius of curvature. Therefore, the size of a pixel must be , small enough to allow a suitable intermediate time step to be chosen. 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 (according to the Gage–Hamilton–Grayson theorem) 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 (when started with all cells in random states) 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 (usual) curvature and and are smooth functions of the orientation . When and (so that the flow is invariant under point reflection), 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 (with a corresponding time scaling) 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 (embedding-dependent) measures such as the mean curvature and intrinsic measures such as the scalar curvature and Ricci curvature. Correspondingly, there are several ways of defining geometric flows based on curvature, including the mean curvature flow (in which the normal speed of an embedded surface is its mean curvature), the Ricci flow (an intrinsic flow on the metric of a space based on its Ricci curvature), the Gauss curvature flow, and the Willmore flow (the gradient flow for an energy functional combining the mean curvature and Gaussian curvature). The curve-shortening flow is a special case of the mean curvature flow and of the Gauss curvature flow for one-dimensional curves. • In real-time path planning for mobile robots, a modified version of the curve-shortening flow with additional forces has been used to find paths that strike a balance between being short and staying clear of obstacles. • 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. ==Notes==