Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGrid peeling and the affine curve-shortening flow
196
0
0.0
(
0
)
Added by
Gabriel Nivasch
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. The first one (which we call grid peeling) is the convex-layer decomposition of subsets $Gsubset mathbb Z^2$ of the integer grid, previously studied for the particular case $G={1,ldots,m}^2$ by Har-Peled and Lidicky (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (1993) and Sapiro and Tannenbaum (1993). We present empirical evidence that, in a certain well-defined sense, grid peeling behaves at the limit like ACSF on convex curves. We offer some theoretical arguments in favor of this conjecture. We also pay closer attention to the simple case where $G=mathbb N^2$ is a quarter-infinite grid. This case corresponds to ACSF starting with an infinite L-shaped curve, which when transformed using the ACSF becomes a hyperbola for all times $t>0$. We prove that, in the grid peeling of $mathbb N^2$, (1) the number of grid points removed up to iteration $n$ is $Theta(n^{3/2}log n)$; and (2) the boundary at iteration $n$ is sandwiched between two hyperbolas that are separated from each other by a constant factor.
rate research
Read More
We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set $Psubset mathbb R^2$ of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and $P$ is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between ACSF and HCS generalizes the link between ACSF and convex-layer decomposition (Eppstein et al., 2017; Calder and Smart, 2020), which is restricted to convex curves. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.
We give the following results for Pinkalls central affine curve flow on the plane: (i) a systematic and simple way to construct the known higher commuting curve flows, conservation laws, and a bi-Hamiltonian structure, (ii) Baecklund transformations and a permutability formula, (iii) infinitely many families of explicit solutions. We also solve the Cauchy problem for periodic initial data.
In this paper we discuss novel numerical schemes for the computation of the curve shortening and mean curvature flows that are based on special reparametrizations. The main idea is to use special solutions to the harmonic map heat flow in order to reparametrize the equations of motion. This idea is widely known from the Ricci flow as the DeTurck trick. By introducing a variable time scale for the harmonic map heat flow, we obtain families of numerical schemes for the reparametrized flows. For the curve shortening flow this family unveils a surprising geometric connection between the numerical schemes in [5] and [9]. For the mean curvature flow we obtain families of schemes with good mesh properties similar to those in [3]. We prove error estimates for the semi-discrete scheme of the curve shortening flow. The behaviour of the fully-discrete schemes with respect to the redistribution of mesh points is studied in numerical experiments. We also discuss possible generalizations of our ideas to other extrinsic flows.
A recent article by the first two authors together with B Andrews and V-M Wheeler considered the so-called `ideal curve flow, a sixth order curvature flow that seeks to deform closed planar curves to curves with least variation of total geodesic curvature in the $L^2$ sense. Critical in the analysis there was a length bound on the evolving curves. It is natural to suspect therefore that the length-constrained ideal curve flow should permit a more straightforward analysis, at least in the case of small initial `energy. In this article we show this is indeed the case, with suitable initial data providing a flow that exists for all time and converges smoothly and exponentially to a multiply-covered round circle of the same length and winding number as the initial curve.
We study the problem of polygonal curve simplification under uncertainty, where instead of a sequence of exact points, each uncertain point is represented by a region, which contains the (unknown) true location of the vertex. The regions we consider are disks, line segments, convex polygons, and discrete sets of points. We are interested in finding the shortest subsequence of uncertain points such that no matter what the true location of each uncertain point is, the resulting polygonal curve is a valid simplification of the original polygonal curve under the Hausdorff or the Frechet distance. For both these distance measures, we present polynomial-time algorithms for this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
