No Arabic abstract
Currents represent generalized surfaces studied in geometric measure theory. They range from relatively tame integral currents representing oriented compact manifolds with boundary and integer multiplicities, to arbitrary elements of the dual space of differential forms. The flat norm provides a natural distance in the space of currents, and works by decomposing a $d$-dimensional current into $d$- and (the boundary of) $(d+1)$-dimensional pieces in an optimal way. Given an integral current, can we expect its flat norm decomposition to be integral as well? This is not known in general, except in the case of $d$-currents that are boundaries of $(d+1)$-currents in $mathbb{R}^{d+1}$ (following results from a corresponding problem on the $L^1$ total variation ($L^1$TV) of functionals). On the other hand, for a discretized flat norm on a finite simplicial complex, the analogous statement holds even when the inputs are not boundaries. This simplicial version relies on the total unimodularity of the boundary matrix of the simplicial complex -- a result distinct from the $L^1$TV approach. We develop an analysis framework that extends the result in the simplicial setting to one for $d$-currents in $mathbb{R}^{d+1}$, provided a suitable triangulation result holds. In $mathbb{R}^2$, we use a triangulation result of Shewchuk (bounding both the size and location of small angles), and apply the framework to show that the discrete result implies the continuous result for $1$-currents in $mathbb{R}^2$.
We describe and provide code and examples for a polygonal edge matching method.
We establish a quantitative lower bound on the reach of flat norm minimizers for boundaries in $mathbb{R}^2$.
We introduce and begin to explore the mean and median of finite sets of shapes represented as integral currents. The median can be computed efficiently in practice, and we focus most of our theoretical and computational attention on medians. We consider questions on the existence and regularity of medians. While the median might not exist in all cases, we show that a mass-regularized median is guaranteed to exist. When the input shapes are modeled by integral currents with shared boundaries in codimension $1$, we show that the median is guaranteed to exist, and is contained in the emph{envelope} of the input currents. On the other hand, we show that medians can be emph{wild} in this setting, and smooth inputs can generate non-smooth medians. For higher codimensions, we show that emph{books} are minimizing for a finite set of $1$-currents in $Bbb{R}^3$ with shared boundaries. As part of this proof, we present a new result in graph theory---that emph{cozy} graphs are emph{comfortable}---which should be of independent interest. Further, we show that regular points on the median have book-like tangent cones in this case. From the point of view of computation, we study the median shape in the settings of a finite simplicial complex. When the input shapes are represented by chains of the simplicial complex, we show that the problem of finding the median shape can be formulated as an integer linear program. This optimization problem can be solved as a linear program in practice, thus allowing one to compute median shapes efficiently. We provide open source code implementing our methods, which could also be used by anyone to experiment with ideas of their own. The software could be accessed at https://github.com/tbtraltaa/medianshape.
Bidimensionality is the most common technique to design subexponential-time parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behind it is a combinatorial lemma of Robertson, Seymour and Thomas that states that every planar graph either has a $sqrt{k}times sqrt{k}$-grid as a minor, or its treewidth is $O(sqrt{k})$. However, bidimensionality theory cannot be extended directly to several well-known classes of geometric graphs. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs. Inspired by this, we prove a new decomposition lemma for map graphs. Informally, our lemma states the following. For any map graph $G$, there exists a collection $(U_1,ldots,U_t)$ of cliques of $G$ with the following property: $G$ either contains a $sqrt{k}times sqrt{k}$-grid as a minor, or it admits a tree decomposition where every bag is the union of $O(sqrt{k})$ of the cliques in the above collection. The new lemma appears to be a handy tool in the design of subexponential parameterized algorithms on map graphs. We demonstrate its usability by designing algorithms on map graphs with running time $2^{O({sqrt{k}log{k}})} cdot n^{O(1)}$ for the Connected Planar $cal F$-Deletion problem (that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms for Longest Cycle/Path and Cycle Packing is more challenging. We have to construct tree decompositions with more powerful properties and to prove sublinear bounds on the number of ways an optimum solution could cross bags in these decompositions. For Longest Cycle/Path, these are the first subexponential-time parameterized algorithms on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known $2^{O({k^{0.75}log{k}})} cdot n^{O(1)}$-time algorithms on map graphs.
In this chapter, we discuss applications of topological data analysis (TDA) to spatial systems. We briefly review the recently proposed level-set construction of filtered simplicial complexes, and we then examine persistent homology in two cases studies: street networks in Shanghai and hotspots of COVID-19 infections. We then summarize our results and provide an outlook on TDA in spatial systems.