 Publication Date:
 NSFPAR ID:
 10280220
 Journal Name:
 Analysis and Geometry in Metric Spaces
 Volume:
 9
 Issue:
 1
 Page Range or eLocationID:
 90 to 119
 ISSN:
 22993274
 Sponsoring Org:
 National Science Foundation
More Like this

Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is βstretch if π is a simple (nonselfintersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the subcurve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the βstretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a βstretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in amore »

Abstract Positive
intermediate Ricci curvature on a Riemannian$$k\mathrm{th}$$ $k\mathrm{th}$n manifold, to be denoted by , is a condition that interpolates between positive sectional and positive Ricci curvature (when$${{\,\mathrm{Ric}\,}}_k>0$$ ${\phantom{\rule{0ex}{0ex}}\mathrm{Ric}\phantom{\rule{0ex}{0ex}}}_{k}>0$ and$$k =1$$ $k=1$ respectively). In this work, we produce many examples of manifolds of$$k=n1$$ $k=n1$ with$${{\,\mathrm{Ric}\,}}_k>0$$ ${\phantom{\rule{0ex}{0ex}}\mathrm{Ric}\phantom{\rule{0ex}{0ex}}}_{k}>0$k small by examining symmetric and normal homogeneous spaces, along with certain metric deformations of fat homogeneous bundles. As a consequence, we show that every dimension congruent to$$n\ge 7$$ $n\ge 7$ supports infinitely many closed simply connected manifolds of pairwise distinct homotopy type, all of which admit homogeneous metrics of$$3\,{{\,\mathrm{mod}\,}}4$$ $3\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\mathrm{mod}\phantom{\rule{0ex}{0ex}}4$ for some$${{\,\mathrm{Ric}\,}}_k>0$$ ${\phantom{\rule{0ex}{0ex}}\mathrm{Ric}\phantom{\rule{0ex}{0ex}}}_{k}>0$ . We also prove that each dimension$$k $k<n/2$ congruent to 0 or$$n\ge 4$$ $n\ge 4$ supports closed manifolds which carry metrics of$$1\,{{\,\mathrm{mod}\,}}4$$ $1\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\mathrm{mod}\phantom{\rule{0ex}{0ex}}4$ with$${{\,\mathrm{Ric}\,}}_k>0$$ ${\phantom{\rule{0ex}{0ex}}\mathrm{Ric}\phantom{\rule{0ex}{0ex}}}_{k}>0$ , but do not admit metrics of positive sectional curvature.$$k\le n/2$$ $k\le n/2$ 
Route reconstruction is an important application for Geographic Information Systems (GIS) that rely heavily upon GPS data and other location data from IoT devices. Many of these techniques rely on geometric methods involving the \frechet\ distance to compare curve similarity. The goal of reconstruction, or map matching, is to find the most similar path within a given graph to a given input curve, which is often approximate location data. This process can be approximated by sampling the curves and using the \dfd. Due to power and coverage constraints, the GPS data itself may be sparse causing improper constraints along the edges during the reconstruction if only the continuous \frechet\ distance is used. Here, we look at two variations of discrete map matching: one constraining the walk length and the other limiting the number of vertices visited in the graph. %, and the constraint that the walk may not selfintersect. We give an efficient algorithm to solve the question based on walk length showing it is in \textbf{P}. We prove the other problem is \npc\ and the minimization variant is \apx\ while also giving a parameterized algorithm to solve the problem.

Abstract We prove that, for every closed (not necessarily convex) hypersurface Σ in ℝ n + 1 {\mathbb{R}^{n+1}} and every p > n {p>n} , the L p {L^{p}} norm of the tracefree part of the anisotropic second fundamental form controls from above the W 2 , p {W^{2,p}} closeness of Σ to the Wulff shape. In the isotropic setting, we provide a simpler proof. This result is sharp since in the subcritical regime p ≤ n {p\leq n} , the lack of convexity assumptions may lead in general to bubbling phenomena.Moreover, we obtain a stability theorem for quasiEinstein (not necessarily convex) hypersurfaces and we improve the quantitative estimates in the convex setting.

Registering functions (curves) using time warpings (reparameterizations) is central to many computer vision and shape analysis solutions. While traditional registration methods minimize penalizedL2 norm, the elastic Riemannian metric and squareroot velocity functions (SRVFs) have resulted in significant improvements in terms of theory and practical performance. This solution uses the dynamic programming algorithm to minimize the L2 norm between SRVFs of given functions. However, the computational cost of this elastic dynamic programming framework – O(nT 2 k) – where T is the number of time samples along curves, n is the number of curves, and k < T is a parameter – limits its use in applications involving big data. This paper introduces a deeplearning approach, named SRVF Registration Net or SrvfRegNet to overcome these limitations. SrvfRegNet architecture trains by optimizing the elastic metricbased objective function on the training data and then applies this trained network to the test data to perform fast registration. In case the training and the test data are from different classes, it generalizes to the test data using transfer learning, i.e., retraining of only the last few layers of the network. It achieves the stateoftheart alignment performance albeit at much reduced computational cost. We demonstrate themore »