Vietoris--Rips Shadow for Euclidean Graph Reconstruction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917534974869504 |
|---|---|
| author | Komendarczyk, Rafal Majhi, Sushovan Mitra, Atish |
| author_facet | Komendarczyk, Rafal Majhi, Sushovan Mitra, Atish |
| contents | The shadow of an abstract simplicial complex $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 $K$. The Vietoris--Rips complex of a metric space $(S,d)$ at scale $β$ is an abstract simplicial complex whose each $k$-simplex corresponds to $(k+1)$ points of $S$ within diameter $β$. In case $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 $π_0$ and $π_1$. We extend the result beyond the standard Euclidean distance on $S\subset\mathbb R^N$ to a family of path-based metrics, $d^\varepsilon_{S}$. From the pairwise Euclidean distances of points in $S$, we introduce a family (parametrized by $\varepsilon$) of path-based Vietoris--Rips complexes $R^\varepsilon_β(S)$ for a scale $β>0$. If $S\subset\mathbb{R}^2$ is Hausdorff-close to a planar Euclidean graph $G$, we provide quantitative bounds on scales $β,\varepsilon$ for the shadow projection map of the Vietoris--Rips complex of $(S,d^\varepsilon_S)$ at scale $β$ to induce $π_1$-isomorphism. This paper first studies the homotopy-type recovery of $G\subset\mathbb R^N$ using the abstract Vietoris--Rips complex of a Hausdorff-close sample $S$ under the $d^\varepsilon_S$ metric. Then, our result on the $π_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 $G$, we quantify the choice of a suitable sample density $\varepsilon$ and a scale $β$ at which the shadow of $R^\varepsilon_β(S)$ is homotopy-equivalent and Hausdorff-close to $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01603 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Vietoris--Rips Shadow for Euclidean Graph Reconstruction Komendarczyk, Rafal Majhi, Sushovan Mitra, Atish Algebraic Topology Computational Geometry The shadow of an abstract simplicial complex $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 $K$. The Vietoris--Rips complex of a metric space $(S,d)$ at scale $β$ is an abstract simplicial complex whose each $k$-simplex corresponds to $(k+1)$ points of $S$ within diameter $β$. In case $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 $π_0$ and $π_1$. We extend the result beyond the standard Euclidean distance on $S\subset\mathbb R^N$ to a family of path-based metrics, $d^\varepsilon_{S}$. From the pairwise Euclidean distances of points in $S$, we introduce a family (parametrized by $\varepsilon$) of path-based Vietoris--Rips complexes $R^\varepsilon_β(S)$ for a scale $β>0$. If $S\subset\mathbb{R}^2$ is Hausdorff-close to a planar Euclidean graph $G$, we provide quantitative bounds on scales $β,\varepsilon$ for the shadow projection map of the Vietoris--Rips complex of $(S,d^\varepsilon_S)$ at scale $β$ to induce $π_1$-isomorphism. This paper first studies the homotopy-type recovery of $G\subset\mathbb R^N$ using the abstract Vietoris--Rips complex of a Hausdorff-close sample $S$ under the $d^\varepsilon_S$ metric. Then, our result on the $π_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 $G$, we quantify the choice of a suitable sample density $\varepsilon$ and a scale $β$ at which the shadow of $R^\varepsilon_β(S)$ is homotopy-equivalent and Hausdorff-close to $G$. |
| title | Vietoris--Rips Shadow for Euclidean Graph Reconstruction |
| topic | Algebraic Topology Computational Geometry |
| url | https://arxiv.org/abs/2506.01603 |