Vietoris--Rips Shadow for Euclidean Graph Reconstruction

Vietoris--Rips Shadow for Euclidean Graph Reconstruction | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Vietoris--Rips Shadow for Euclidean Graph Reconstruction Rafal Komendarczyk, Sushovan Majhi, Atish Mitra This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7842156/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 9 You are reading this latest preprint version Abstract 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) Vietoris–Rips complex graph reconstruction geometric graphs homotopy Equivalence geometric complex shadow complex Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Revision requested 04 Mar, 2026 Reviews received at journal 10 Feb, 2026 Reviews received at journal 01 Feb, 2026 Reviewers agreed at journal 21 Dec, 2025 Reviewers agreed at journal 19 Dec, 2025 Reviewers invited by journal 08 Dec, 2025 Editor assigned by journal 14 Oct, 2025 Submission checks completed at journal 13 Oct, 2025 First submitted to journal 12 Oct, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7842156","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":557369033,"identity":"86bdb9bb-e4cd-4f3d-b340-5ae2d551b08d","order_by":0,"name":"Rafal Komendarczyk","email":"","orcid":"","institution":"Tulane University","correspondingAuthor":false,"prefix":"","firstName":"Rafal","middleName":"","lastName":"Komendarczyk","suffix":""},{"id":557369036,"identity":"69200697-3c3d-490e-9a16-ce4a1bf145bd","order_by":1,"name":"Sushovan Majhi","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAvElEQVRIiWNgGAWjYLACyQYJOQiLjQQtxiRqYWxgSGwgWot8A3fiB8sdFunzI3IMGD6UHSasxeAA72YJyTMSuRtv5BgwzjhHjBYG3g0Skm1ALbNzDJh524jQIt/Au/kHUEu6IUjLX2K0MBzg3QayJUFeGqiFkRgtBod5t1kAtRhukH9WcLDnXDoRDmvv3Xxbsq1OXr7n8MYHP8qsiXAYMxBJgKw7AHQkEeohgPEDyLoGotWPglEwCkbBSAMAwtA21Qv3RMMAAAAASUVORK5CYII=","orcid":"","institution":"George Washington University","correspondingAuthor":true,"prefix":"","firstName":"Sushovan","middleName":"","lastName":"Majhi","suffix":""},{"id":557369037,"identity":"d2abbe3f-d67d-4c15-9069-8aedbf9a5c4e","order_by":2,"name":"Atish Mitra","email":"","orcid":"","institution":"Montana Technological University","correspondingAuthor":false,"prefix":"","firstName":"Atish","middleName":"","lastName":"Mitra","suffix":""}],"badges":[],"createdAt":"2025-10-12 17:08:19","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7842156/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7842156/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":98422054,"identity":"3cc084eb-984a-4735-8ebb-6c6fd29ce40d","added_by":"auto","created_at":"2025-12-17 16:30:23","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":5356,"visible":true,"origin":"","legend":"","description":"","filename":"5dd912290379404cb696ae4474eb39d2.json","url":"https://assets-eu.researchsquare.com/files/rs-7842156/v1/a57bb2bc6f69051ec5e3d92c.json"},{"id":98443609,"identity":"73a5af89-5f51-4430-9ab4-d0ce214c32c1","added_by":"auto","created_at":"2025-12-17 17:13:51","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":845629,"visible":true,"origin":"","legend":"","description":"","filename":"shadowJACT.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7842156/v1_covered_b7325ce9-8307-40f1-8dc5-8ca9d22f9607.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Vietoris--Rips Shadow for Euclidean Graph Reconstruction","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"journal-of-applied-and-computational-topology","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"apct","sideBox":"Learn more about [Journal of Applied and Computational Topology](https://www.springer.com/journal/41468)","snPcode":"41468","submissionUrl":"https://submission.springernature.com/new-submission/41468/3","title":"Journal of Applied and Computational Topology","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Vietoris–Rips complex, graph reconstruction, geometric graphs, homotopy Equivalence, geometric complex, shadow complex","lastPublishedDoi":"10.21203/rs.3.rs-7842156/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7842156/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eThe 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\u0026gt;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$.\u003c/p\u003e\n\u003cp\u003eMSC Classification 2020: 55P10 (Primary) , 55N31 , 54E35 (Secondary)\u003c/p\u003e","manuscriptTitle":"Vietoris--Rips Shadow for Euclidean Graph Reconstruction","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-12-11 05:49:44","doi":"10.21203/rs.3.rs-7842156/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2026-03-04T07:59:22+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-02-10T16:04:58+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-02-01T08:12:29+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"244293281089447659950237761664325370572","date":"2025-12-21T14:36:48+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"231057195566779605186223939191036208733","date":"2025-12-19T17:15:51+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-12-08T20:43:57+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-10-14T19:30:27+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-10-13T15:20:26+00:00","index":"","fulltext":""},{"type":"submitted","content":"Journal of Applied and Computational Topology","date":"2025-10-12T17:02:11+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"journal-of-applied-and-computational-topology","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"apct","sideBox":"Learn more about [Journal of Applied and Computational Topology](https://www.springer.com/journal/41468)","snPcode":"41468","submissionUrl":"https://submission.springernature.com/new-submission/41468/3","title":"Journal of Applied and Computational Topology","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"f3f590f8-d28d-4740-973c-e46894db9ccb","owner":[],"postedDate":"December 11th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-05-17T10:38:17+00:00","versionOfRecord":[],"versionCreatedAt":"2025-12-11 05:49:44","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7842156","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7842156","identity":"rs-7842156","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}