Visualizing paths in configuration space

The goal of this post is to visualize how point configurations induce persistent homology, and how paths between point samples induce changes in the simplicial complexes producing the homology. We use the Čech simplicial complex construction of a finite subset of $\R^N$.

Definition: For $M$ a Riemannian mandifold, $\Conf_n(M):= \{P\subseteq M : |P|=n\}$ is the configuration space of $n$ points on $M$.

The space $\Conf_n(M)$ is itself a topological space, with topology induced by the Hausdorff distance of subsets. Let $\SC$ be the set of abstract simplicial complexes $(V,S)$, where $V$ is a set and $S\subseteq P(V)$ closed under subsets. Let $\uSC$ be the set of unlabeled abstract simplicial complexes, with the natural projection map $\SC\to \uSC$.

Definition: The Čech map is the function $\check C\colon \Conf_n(M)\times \R_{\geqslant 0}\to \SC$ given by $V(\check C(P,r))=P$ and $P'\in S(\check C(P,r))$ whenever $\bigcap_{p\in P'} B(p,r) \neq \emptyset$, for every $P'\subseteq P$. The unlabeled Čech map is the composition of $\check C$ with the projection to $\uSC$.

We will consider the case $M=\R^2$ and $n=4$. To describe an implementation of the Čech map, we only need to consider double and triple intersections. Finding if $B(P_1,r)\cap B(P_2,r)$ is empty or not is easy, but to determine if $B(P_1,r)\cap B(P_2,r)\cap B(P_3,r)$ is empty or not requires more care. Below is an implementation in Mathematica.

(* CechPt : Finds the coordinate where balls of the same radii around a,b,c will first intersect *)
(* Input : 3 coordinates {x, y}. Output : 1 coordinate {x, y} *)
CechPt[a_,b_,c_] := Module[{
    cenx = Det[{{Norm[a]^2, a[[2]], 1}, {Norm[b]^2, b[[2]], 1}, {Norm[c]^2, c[[2]], 1}}],
    ceny = Det[{{a[[1]], Norm[a]^2, 1}, {b[[1]], Norm[b]^2, 1}, {c[[1]], Norm[c]^2, 1}}],
    scal = 2*Det[{{a[[1]], a[[2]], 1}, {b[[1]], b[[2]], 1}, {c[[1]], c[[2]], 1}}]},
   cen = {cenx/scal, ceny/scal};
   If[Max[ArcCos[(b-a).(c-a)/(Norm[b-a]*Norm[c-a])],
           ArcCos[(a-b).(c-b)/(Norm[a-b]*Norm[c-b])],
           ArcCos[(a-c).(b-c)/(Norm[a-c]*Norm[b-c])]] < Pi/2, cen,
     If[Norm[cen-(a+b)/2] < Norm[cen-(a+c)/2],
       If[Norm[cen-(a+b)/2] < Norm[cen-(b+c)/2], (a+b)/2, (b+c)/2],
       If[Norm[cen-(a+c)/2] < Norm[cen-(b+c)/2], (a+c)/2, (b+c)/2]]]];

Here cen is the circumcenter of the input points, which corresponds to our desired point only if it lies within the convex hull of the points. Now $B(P_1,r)\cap B(P_2,r)\cap B(P_3,r)$ is non-empty if and only if the distance from each of $P_1$, $P_2$, $P_3$ to CechPt[$P_1$, $P_2$, $P_3$] is less than or equal to $r$.

Let $\gamma\colon I\to \Conf_4(\R^2)$ be a path, and $\gamma(0)= \{P_1,P_2,P_3,P_4\}$. At each $t\in I$ and for every pair and triple $P'\subseteq\gamma(t)$, we can find the smallest $r$ such that $\bigcap_{p\in P'}B(P,r)\neq \emptyset$. This gives 6 curves for the pairs $P'$, and 4 curves for the triples $P'$, which we can plot all together in Mathematica.

PList[t_] := {P1[t],P2[t],P3[t],P4[t]};
(* Graphs of pairwise distances *)
DistGraph1 = Plot[Table[Norm[pair[[1]]-pair[[2]]]/2, {pair,Subsets[PList[t],{2}]}], 
               {t, 0, 1}, PlotRange -> {{0,1},{0,1.5}}, PlotStyle -> {Gray}, AspectRatio -> 1];
(* Graphs of minimum distance from every triple to its CechPt*)
DistGraph2 = Plot[Table[Max[
                  Table[Norm[triple[[k]]-CechPt@@triple],{k,1,3}]], {triple,Subsets[PList[t],{3}]}],
               {t, 0, 1}, PlotRange -> {{0,1},{0,1.5}}, PlotStyle -> {Orange}, AspectRatio -> 1];

The code is given so that it may be easily generalized to more than 4 points. Next, use the Manipulate command to add interactivity to the graphs.

Manipulate[{
  Show[DistGraph2, DistGraph1],
  Show[
    ParametricPlot[PList[t],{t,0,X[[1]]},PlotRange -> {{-2,2},{-2,2}},PlotStyle -> {Black}],
    Graphics[Join[
      {Opacity[.2],Red}, Table[Disk[point,X[[2]]],{point,PList[X[[1]]]}],
      {Opacity[1],Red}, Table[Circle[point,X[[2]]],{point,PList[X[[1]]]}],
      {Red,Disk[P1[X[[1]]],.05]},
      {Blue,Disk[P2[X[[1]]],.05]},
      {Darker[Green],Disk[P3[X[[1]]],.05]},
      {Yellow,Disk[P4[X[[1]]],.05]}]]],
  Graphics[Join[
    {Black, Thick},
    Flatten[Table[{{Opacity[0], Opacity[.3]}[[Boole[X[[2]] >= Norm[pair[[1]][[1]][X[[1]]] 
               - pair[[2]][[1]][X[[1]]]]/2] + 1]], Line[#[[2]]&/@pair]},
               {pair,Subsets[{{P1,{0,0}},{P2,{2,0}},{P3,{0,2}},{P4,{2,2}}},{2}]}]],
    Flatten[Table[{{Opacity[0], Opacity[.3]}[[Boole[X[[2]] >= Max[Table[Norm[triple[[k]][[1]][X[[1]]]
               - CechPt@@(#[[1]][X[[1]]]&/@triple)], {k,1,3}]]] + 1]], Polygon[#[[2]]&/@triple]},
               {triple,Subsets[{{P1,{0,0}},{P2,{2,0}},{P3,{0,2}},{P4,{2,2}}},{3}]}]],
    {Opacity[1], Red, Disk[{0,0},.07], Blue, Disk[{2,0},.07], Darker[Green], Disk[{0,2},.07],
               Yellow, Disk[{2,2},.07]}]]
  }, {{X, {.1, .1}}, Locator}]

This produces the interactive visualization below, allowing the user to drag the crosshairs on the graph on the left (graphs of when double and triple intersections are reached). The paths of the individual points $P_1,P_2,P_3,P_4$ are in the middle and the image of the unlabeled Čech map is on the right.

The graphs on the left stratify the strip $I\times \R_{\geqslant 0}$, so that the unlabeled Čech map is constant on each stratum. Computing the Betti numbers of each simplicial complex gives the CROCKER plot (see TZH) of the stratified space. We use the Čech instead of the Rips complex, so perhaps this should be called the CROCKEČ plot. The stratified space, 0-dimensional, and 1-dimensional plots are given below.

Here the Betti numbers were computed by inspection, since the complexes are so small. An extension would be to make this computation automatic once the input path $\gamma$ is given.

The Mathematica code for this post is available online.

References: Topaz, Ziegelmeier, Halverson (Topological Data Analysis of Biological Aggregation Models)

Artin gluing a sheaf 2: simplicial sets and configuration spaces

The goal of this post is to extend the previous stratifying map to simplicial sets, and to generalize the sheaf construction to $X = \Conf_n(M)\times \R_{\geqslant 0}$ for arbitrary integers $n$, where $M$ is a smooth, compact, connected manifold. We work with $\Conf_n(M)$ instead of $\Ran^{\leqslant n}(M)$ because Lemma 1 and Proposition 2 have no chance of extending to $\Ran^{\leqslant n}(M)$ without major modifications (see Remark 3 at the end of this post).

Recall $SC$ is the category of simplicial complexes and simplicial maps, with $SC_n$ the full subcategory of simplicial complexes on $n$ vertices. Our main function is \[ \begin{array}{r c c c l}
f\ :\ X & \tov{f_1} & SC & \tov{f_2} & \sSet, \\
(P,a) & \mapsto & VR(P,a) & \mapsto & \Hom_{\Set}(\Delta^\bullet,VR(P,a)).
\end{array} \] On $\Conf_n(M)$ we have a natural metric, the Hausdorff distance $d_H(P,Q) = \max_{p\in P}\min_{q\in Q}d(p,q)+\max_{q\in Q}\min_{p\in P}d(p,q)$. This induces the 1-product metric on $X$, as \[ d_X((P,a),(Q,b)) = d_H(P,Q) + d(a,b), \] where $d$ without a subscript is Euclidean distance. We could have chosen any other $p$-product metric, but $p=1$ makes computations easier. For a given $(P,t)\in X$, write $P = \{P_1,\dots,P_n\}$ and define its maximal neighborhood to be the ball $B_X(\min\{\delta_1,\delta_2,t\},P)$, where \[ \delta_1 = \min_{i<j}\{d(P_i,P_j)\},
\hspace{1cm}
\delta_2 = \min_{i<j}\{|d(P_i,P_j)-t|\ :\ d(P_i,P_j)\neq t\}. \]

Lemma 1: Any path $\gamma:I\to X$ induces a unique morphism $f(\gamma(0))\to f(\gamma(1))$ of simplicial sets.

Proof: Write $\gamma(0) = \{P_1,\dots,P_n\}$ and $\gamma(1) = \{Q_1,\dots,Q_n\}$. The map $\gamma$ induces $n$ paths $\gamma_i:I\to M$ for $i=1,\dots,n$, with $\gamma_i$ the path based at $P_i$. Let $s:\gamma(0)\to \gamma(1)$ be the map on simplicial complexes defined by $P_i\mapsto \gamma_i(1)$. Since we are in the configuration space, where points cannot collide (as opposed to the Ran space), this is a well-defined map. Then $f_2(s)$ is a morphism of simplicial complexes. $\square$

Note the morphism of simplicial sets induced by any path in a maximal neighborhood of $x\in X$ is the identity morphism. We now move to describing a sheaf over all of $X$.

Definition: Let $X$ be any topological space and $\mathcal C$ a category with pullbacks. Let $A\subseteq X$ open and $B=X\setminus A \subseteq X$ closed, with $i:A\hookrightarrow X$ and $j:B\hookrightarrow X$ the inclusion maps. Let $\mathcal F$ be a $\mathcal C$-valued sheaf on $A$ and $\mathcal G$ a $\mathcal C$-valued sheaf on $B$. Then the \emph{Artin gluing} of $\mathcal F$ and $\mathcal G$ is the $\mathcal C$-valued sheaf $\mathcal H$ on $X$ defined as the pullback, or fiber product, of $i_*\mathcal F$ and $j_*\mathcal G$ over $j_*j^*i_*\mathcal F$ in the diagram below.

Note the definition requires a choice of sheaf map $\varphi:\mathcal G\to j^*i_*\mathcal F$. In the proof below, this sheaf map will be the morphism of simplicial sets from Lemma 1 through the functor $\Hom_\Set(\Delta^\bullet,-) = f_2(-)$.

Recall the ordering of $SC_n$ described by the only definition in a previous post ("Exit paths, part 2," 2017-09-28). Fix a cover $\{A_i\}_{i=1}^{N}$ of $SC_n$ by nested open subsets (so $N=|SC_n|$), with $B_i := f_1^{-1}(A_i)$ and $B_{\leqslant i} := \bigcup_{j=1}^i B_i$. We now have an induced order on and cover of $\im(f)=\sSet'$, as a full subcategory of $\sSet$. Even more, we now have an induced total order on $\sSet' = \{S_1,\dots,S_N\}$, with $S_i$ the unique simplicial set in $A_i\setminus A_{i-1}$. For example, $S_1=\Hom_\Set(\Delta^\bullet,\Delta^n)$ and $S_{N}=\Hom_\Set(\Delta^\bullet,\bigcup_{i=1}^n\Delta^0)$.

For ease of notation, we let $B_0 = \emptyset$ and write $S_\emptyset = \Hom(\Delta^\bullet,\emptyset)$, $S_0 = \Hom(\Delta^\bullet,\Delta^0)$.

Definition 1: Let $\mathcal F_i:\Op(B_i)^{op}\to \sSet$ be the locally constant sheaf given by $\mathcal F_i(U_x) = S_i$, where $U_x$ is a subset of the maximal neighborhood of $x\in B_i$. In general, \[ \mathcal F_i(U) = \begin{cases}
S_i & \text{ if }\begin{array}[t]{l}U\neq \emptyset, \\U\text{ is path connected},\\\text{every loop }\gamma:I\to U\text{ induces }\id:f(\gamma(0))\to f(\gamma(1)),\end{array} \\
S_\emptyset & \text{ else if }U\neq\emptyset, \\
S_0 & \text{ else.}
\end{cases} \] In general, we say $U\subseteq X$ is good if it is non-empty, path connected, and every loop $\gamma:I\to U$ induces the identity morphism on simplicial sets.

Proposition 2: Let $\mathcal F_{\leqslant 1} = \mathcal F_1$, and $\mathcal F_{\leqslant i}$ be the sheaf on $B_{\leqslant i}$ obtained by Artin gluing $\mathcal F_i$ onto $\mathcal F_{\leqslant i-1}$, for all $i=2,\dots,N$. Then $\mathcal F = \mathcal F_{\leqslant N}$ is the $SC_n$-constructible sheaf on $X$ described by \[ \mathcal F(U) = \begin{cases}
S_{\max\{1\leqslant \ell\leqslant N\ :\ U\cap B_{\ell}\neq \emptyset\}} & \text{ if $U$ is good,}\\
S_\emptyset & \text{ else if }U\neq\emptyset, \\
S_0 & \text{ else.}
\end{cases} \hspace{2cm} (1) \]

Proof: We proceed by induction. Begin with the constant sheaf $\mathcal F_1$ on $B_1$ and $\mathcal F_2$ on $B_2$, which we would like to glue together to get a sheaf $\mathcal F_{\leqslant2}$ on $B_{\leqslant 2}$. Since $f_1$ is continuous in the Alexandrov topology on the poset $SC_{\leqslant n}$, $B_1\subseteq B_{\leqslant 2}$ is open and $B_2 \subseteq B_{\leqslant 2}$ is closed. Let $i:B_1\hookrightarrow B_{\leqslant 2}$ and $j:B_2\hookrightarrow B_{\leqslant 2}$ be the inclusion maps. The sheaf $j^*i_*\mathcal F_1$ has support $\closure(B_1)\cap B_2 \neq \emptyset$ with \[ j^*i_*\mathcal F_1(U) = \colim_{V\supseteq j(U)}\left[i_*\mathcal F_1(V)\right] = \colim_{V\supseteq U}\left[\mathcal F_1(V\cap B_1)\right] = \begin{cases}
S_1 & \text{ if }U\cap \closure(B_1)\text{ is good}, \\ S_\emptyset & \text{ else},
\end{cases} \] for any non-empty $U\subseteq B_2$. Let the sheaf map $\varphi:\mathcal F_2\to j^*i_*\mathcal F_1$ be the inclusion simplicial set morphism on good sets (it can be thought of as induced through Lemma 1 by a path starting in $U\cap B_2$ and ending in $V\cap B_1$, for $V$ a small enough set in the colimit above). Note that $S_2 = \Hom_\Set(\Delta^\bullet,\Delta^n\setminus \Delta^1)$, where $\Delta^n\setminus \Delta^1$ is the simplicial complex resulting from removing an edge from the complete simplicial complex on $n$ vertices. Let $\mathcal F_{\leqslant 2}$ be the pullback of $i_*\mathcal F_1$ and $j_*\mathcal F_2$ along $j_*j^*i_*\mathcal F_1$, and $U\subseteq B_{\leqslant 2}$ a good set. If $U\subseteq B_1$, then $\mathcal F_{\leqslant 2}(U) = \mathcal F_1(U)=S_1$, and if  $U\subseteq B_2$, then $\mathcal F_{\leqslant 2}(U) = \mathcal F_2(U) = S_2$. Now suppose that $U\cap B_1 \neq \emptyset$ but also $U\cap B_2\neq\emptyset$, which, since $U$ is good, implies that $U\cap \closure(B_1)\cap B_2\neq\emptyset$. Then we have the pullback square

If $U$ is not good, then the simplicial sets are $S_\emptyset$ or $S_0$, with nothing interesting going on. The pullback over a good set $U$ can be computed levelwise as \[ \mathcal F_{\leqslant 2}(U)_m = \{(\alpha,\beta)\in (S_1)_m\times (S_2)_m\ :\ \alpha=j_*\varphi(\beta)\}. \hspace{2cm} (2)\] Since $j_*\varphi$ is induced by the inclusion $\varphi$, it is the identity on its image. So $\alpha = j_*\varphi(\beta)$ means $\alpha=\beta$, or in other words, $\mathcal F_{\leqslant 2}(U)=S_2$. Hence for arbitrary $U\subseteq B_{\leqslant 2}$, we have \[ \mathcal F_{\leqslant 2}(U) = \begin{cases}
S_{\max\{\ell=1,2\ :\ U\cap B_{\ell}\neq \emptyset\}} & \text{ if $U$ is good,}\\
S_\emptyset & \text{ else if }U\neq\emptyset, \\
S_0 & \text{ else.}
\end{cases}\]

For the inductive step with $k>1$, let $\mathcal F_{\leqslant k}$ be the sheaf on $B_{\leqslant k}$ defined as in Equation (1), but with $k$ instead of $N$. We would like to glue $\mathcal F_{\leqslant k}$ to $\mathcal F_{k+1}$ on $B_{k+1}$ to get a sheaf $\mathcal F_{\leqslant k+1}$ on $B_{\leqslant k+1}$. As before, $B_k \subseteq B_{\leqslant k+1}$ is open and $B_{k+1}\subseteq B_{\leqslant k+1}$ is closed. For $i:B_k\hookrightarrow B_{\leqslant k+1}$ and $j:B_{k+1}\hookrightarrow B_{\leqslant k+1}$ the inclusion maps, the sheaf $j^*i_*\mathcal F_{\leqslant k}$ has support $\closure(B_{\leqslant k})\cap B_{k+1}$, with \[ j^*i_*\mathcal F_{\leqslant k}(U) = \colim_{V\supseteq j(U)}\left[i_*\mathcal F_{\leqslant k}(V)\right] = \colim_{V\supseteq U}\left[\mathcal F_{\leqslant k}(V\cap B_{\leqslant k})\right] = \begin{cases} S_{\max\{1\leqslant \ell\leqslant k\ :\ U\cap \closure(B_\ell)\neq\emptyset\}} & \text{ if }U\cap \closure(B_{\leqslant k})\text{ is good,} \\ S_\emptyset & \text{ else,} \end{cases} \] for any non-empty $U\subseteq B_{k+1}$. Let the sheaf map $\varphi:\mathcal F_{k+1}\to j^*i_*\mathcal F_{\leqslant k}$ be the inclusion simplicial set morphism on good sets (it can be thought of as induced through Lemma 1 by a path starting in $U\cap B_{k+1}$ and ending in $V\cap B_{\leqslant k}$, for $V$ a small enough set in the colimit above). For $U\subseteq B_{\leqslant k+1}$ a good set, if $U\subseteq B_{\leqslant k}$, then $\mathcal F_{\leqslant k+1}(U) = \mathcal F_{\leqslant k}(U)$, and if  $U\subseteq B_{k+1}$, then $\mathcal F_{\leqslant k+1}(U) = \mathcal F_{k+1}(U) = S_{k+1}$. Now suppose that $U\cap B_{\leqslant k} \neq \emptyset$ but also $U\cap B_{k+1}\neq\emptyset$, which, since $U$ is good, implies that $U\cap \closure(B_{\leqslant k})\cap B_{k+1}\neq\emptyset$. Then we have the pullback square

If $U$ is not good, then the simplicial sets are $S_\emptyset$ or $S_0$, with nothing interesting going on. Again, as in Equation (2), the pullback $\mathcal F_{\leqslant k+1}$ on a good set $U$ is \[ \mathcal F_{\leqslant k+1}(U)_m = \{(\alpha,\beta)\in (S_\ell)_m\times (S_{k+1})_m\ :\ \alpha = j_*\varphi(\beta)\}, \] and as before, this implies that $\mathcal F_{\leqslant k+1}(U) = S_{k+1}$. Hence $\mathcal F_{\leqslant k+1}$ is exactly of the form as in Equation (1), with $k+1$ instead of $N$, and by induction we get the desired description for $\mathcal F_{\leqslant N}= \mathcal F$.  $\square$

Remark 3: The statements given in this post do not extend to $\Ran^{\leqslant n}(M)$, at least not as stated. Lemma 1 fails if  somewhere along the path $\gamma$ a point splits in two or more points, as there is no canonical choice which of the "new" points should be the image of the "old" point. This means that the proof of Proposition 2 will also fail, because we relied on a uniquely defined sheaf map $\varphi$ between strata.

Next, we hope to use this approach to describe classic persistent homology results, and maybe link this to the concept of persistence modules.

References: Milne (Etale cohomology, Chapter 2.3)