Vietoris--Rips Shadow for Euclidean Graph Reconstruction

The shadow of an abstract simplicial complex $\mathcal{K}$ with vertices in $\mathbb{R}^N$ is a subset of $\mathbb{R}^N$ defined as the union of the convex hulls of simplices of $\mathcal{K}$. The Vietoris--Rips complex of a metric space $(\mathcal S,d)$ at scale $\beta$ is an abstract simplicial complex whose each $k$-simplex corresponds to $(k+1)$ points of $\mathcal S$ within diameter $\beta$. In case $\mathcal{S}\subset\mathbb R^2$ and $d(a,b)=\|a-b\|$ the standard Euclidean metric, the natural shadow projection of the Vietoris--Rips complex is already proved by Chambers et al. to induce isomorphisms on $\pi_0$ and $\pi_1$. We extend the result beyond the standard Euclidean distance on $\mathcal{S}\subset\mathbb{R}^N$ to a family of path-based metrics, $d^\varepsilon_{\mathcal S}$. From the pairwise Euclidean distances of points in $\mathcal S$, we introduce a family (parametrized by $\varepsilon$) of path-based Vietoris--Rips complexes $\mathcal{R}^\varepsilon_\beta(\mathcal S)$ for a scale $\beta>0$. If $\mathcal{S}\subset\mathbb{R}^2$ is Hausdorff-close to a planar Euclidean graph $\mathcal G$, we provide quantitative bounds on scales $\beta,\varepsilon$ for the shadow projection map of the Vietoris--Rips complex of $(\mathcal{S},d^\varepsilon_\mathcal{S})$ at scale $\beta$ to induce $\pi_1$-isomorphism. This paper first studies the homotopy-type recovery of $\mathcal G\subset\mathbb R^N$ using the abstract Vietoris--Rips complex of a Hausdorff-close sample $\mathcal{S}$ under the $d^\varepsilon_\mathcal{S}$ metric. Then, our result on the $\pi_1$-isomorphism induced by the shadow projection lends itself to providing also a geometrically close embedding for the reconstruction. Based on the length of the shortest loop and large-scale distortion of the embedding of $\mathcal G$, we quantify the choice of a suitable sample density $\varepsilon$ and a scale $\beta$ at which the shadow of $\mathcal{R}^\varepsilon_\beta(\mathcal{S})$ is homotopy-equivalent and Hausdorff-close to $\mathcal G$. MSC Classification 2020: 55P10 (Primary) , 55N31 , 54E35 (Secondary)