# On discrete version of curve shortening flow

One can define an analogous version of the curve shortening flow for polygons in $\mathbb R^2$, namely defined by the differential equation $\dot{p_i}(t)=\frac{v_i(t)}{|v_i(t)|^2}$, where $p_i$ is the $i$-th vertex of the polygon and and $v_i$ is the vector that goes from $p_i$ to the circumcenter of the triangle defined by $p_{i-1}$, $p_i$ and $p_{i+1}$.

The Gage-Hamilton-Grayson theorem states that simple curves remain simple under the curve-shortening flow.

Does this still hold for polygons under this analogous flow?

• I guess it depends on the discretization. If you start with convex (simple) polygons, many discrete flows will preserve convexity (and simplicity). See an example in cims.nyu.edu/~benarous/Publications/benarous_46.pdf Dec 11, 2013 at 5:53

Not exactly an answer to your question, but Peter Scott and I worked out a polygonal flow that is guaranteed to keep curves embedded in "Shortening Curves on Surfaces", Topology 33, (1994) 25-43.

A version of this is implemented in java at disk flow applet

The problem with the Birkhoff flow is that long segments move faster than short segments, and can overtake them, creating self-intersections. This can be overcome by getting the length of segments from the surface (using intersections with some sort of grid for example) rather than from a parametrization of the domain, as with Birkhoff.

This is not a direct answer, but may I point you to an earlier question of Ryan Budney, and to the paper by Bennett Chow and David Glickenstein,

"Semidiscrete Geometric Flows of Polygons." American Mathematical Monthly. April 2007. (MAA link)

Under their discrete flow, every simple polygon converges to a point whose shape is asymptotically an affine transformation of a regular polygon.

• The thing is that simple polygons do not remain simple under the flow studied by Bennett Chow and David Glickenstein as pointed in "Curve Shortening and the Rendezvous Problem for Mobile Autonomous Robots" arxiv.org/pdf/cs.RO/0605070.pdf Dec 10, 2013 at 20:06
• I think the problem relies in the fact that in this case you can split the differential equation in the x and y coordinates. Dec 10, 2013 at 20:09
• @GerardoArizmendi: Yes, you are correct. I am not aware of a definition of discrete flow that guarantees simplicity---I'll be interested to learn! Of course you could always round out the vertices and apply a smooth flow, but then it is no longer discrete. Dec 10, 2013 at 20:10

A related flow does keep simple, see Ileana Streinu's (Joseph's colleague at Smith!) work http://cs.smith.edu/~streinu/Research/robotics.html and related work by Connelly/Demaine/Rote

• Yes, and see my pictures at an answer to Ryan's question here. But arguably, these are not discrete curve-shortening flows... Dec 11, 2013 at 0:56
• I would argue that these are very close to curve-shortening flows. Dec 11, 2013 at 1:04
• Interesting links! Dec 11, 2013 at 1:23

I think this is a very interesting question. However, my answer is that the Gage-Hamilton-Grayson theorem probably not holds for your curvature flow.

I just write a program in metapost, which indicates under your flow, the vertex will move "linearly" (on a line), I believe you can prove that strictly, and from which we can conclude that for some simple curve will have intersections when time goes to infinity.

Here is an example of the output:

The SVG (which can be scaled) can be download from my cloud storage.

In the graph, the initial polygon is draw by blue, and the final polygon is draw by red. I distinguish each step by dashed line.

The initial 20-polygon is given by

(luamplib)               {randomseed:=164.13048854794684}
(luamplib)               >> "z[1]= (7.1663813354355792,2.115410943910577)"
(luamplib)               {randomseed:=1282.7618269274324}
(luamplib)               >> "z[2]= (6.1198547032965198,3.1294415485934794)"
(luamplib)               {randomseed:=403.39625352345581}
(luamplib)               >> "z[3]= (5.3874308800111868,4.8324648551767311)"
(luamplib)               {randomseed:=3339.1733235391926}
(luamplib)               >> "z[4]= (3.5465950228343885,6.1858621289233282)"
(luamplib)               {randomseed:=1839.1381135784272}
(luamplib)               >> "z[5]= (1.2672314185221965,7.8164049682362586)"
(luamplib)               {randomseed:=3420.0974717036256}
(luamplib)               >> "z[6]= (-3.7256314873696939,6.8671219483403938)"
(luamplib)               {randomseed:=510.18410242830026}
(luamplib)               >> "z[7]= (-5.6650842541666693,6.4155586555366675)"
(luamplib)               {randomseed:=12.746562895524596}
(luamplib)               >> "z[8]= (-7.3959720323999152,5.2194560696781931)"
(luamplib)               {randomseed:=1303.1675809171504}
(luamplib)               >> "z[9]= (-6.7246625396621438,1.5797575825552226)"
(luamplib)               {randomseed:=1827.3952890813218}
(luamplib)               >> "z[10]= (-9.1673328058487815,-0.45325023466673714)"
(luamplib)               {randomseed:=7.8023681259649997}
(luamplib)               >> "z[11]= (-9.510793507129911,-3.9190636005348356)"
(luamplib)               {randomseed:=1418.1949241054936}
(luamplib)               >> "z[12]= (-7.425895076183326,-4.2579680419470947)"
(luamplib)               {randomseed:=1480.3974041179326}
(luamplib)               >> "z[13]= (-3.3223499681157214,-6.4744847060536879)"
(luamplib)               {randomseed:=876.68583251129962}
(luamplib)               >> "z[14]= (-1.8601946468263932,-6.6736668112858331)"
(luamplib)               {randomseed:=2646.6707481852013}
(luamplib)               >> "z[15]= (-0.45124071673288363,-9.4417326012844018)"
(luamplib)               {randomseed:=132.57237941859191}
(luamplib)               >> "z[16]= (2.9170180427407999,-8.5078926786590099)"
(luamplib)               {randomseed:=1047.8092142440955}
(luamplib)               >> "z[17]= (4.2494809218946745,-6.7105559485829076)"
(luamplib)               {randomseed:=2021.5000778674312}
(luamplib)               >> "z[18]= (8.0277937535304655,-3.4644864211184609)"
(luamplib)               {randomseed:=2055.7357077356655}
(luamplib)               >> "z[19]= (10.187937026289996,-3.2670946608207374)"
(luamplib)               {randomseed:=3756.315583007492}
(luamplib)               >> "z[20]= (8.0942754644586294,-0.78244053305555517)"