 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.

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δclose to the property in relative Hamming distance or (ii) only a tiny fraction of members are δclose to the property. In particular, no set in the collection has roughly half of its members δclose to the property and the others δfar from it. We show that the collection of affine spaces displays a proximity gap with respect to ReedSolomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/GuruswamiSudan listdecoding bound of the RS code. We also show nearoptimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fq n , every affine space is either entirely δclose to the code, or alternatively at most an ( n/q)fraction of it is δclose to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multipartymore »