Shape Reconstruction

Sushovan MAJHI
Tulane University
October 8, 2019

smajhi.com/recon-presentation

Manifest of the Talk

• Shape Reconstruction Project
• Demo of the Reconstruction Software
• How I made this presentation
• 🍕 Pizza, Discussions, and Questions

Project Timeline

• 2016 Carola's talk on trajectory-based Map Construction
• Jan, 2017 Proposed topological map construction
• Nov, 2017 Topological and Geometric Reconstruction of Metric Graphs in $\mathbb{R}^N$
Fall Workshop on Computational Geometry 2017, Stony Brook, NY
• Nov, 2018 Topological and Geometric Reconstruction of Geodesic Subspaces of $\mathbb{R}^N$
• May, 2019 JS-Based Webapp for visualization software

Collaborators

Carola Wenk
Computer Science, Tulane

Brittany Fasy
Computer Science, Montana State

Rafal Komendarczyk
Mathematics, Tulane

Shapes

Manifolds (the good ones)

Non-manifolds (the bad ones)

Our shapes of interest (the ugly ones)

Problem Statement

We aim to reconstruct an unknown shape $X$.
• $X$ is a (compact) non-manifold
• $X$ is a geodesic space
• We have a sample or a point-cloud $S$ represented as a metric space$(S,d_S)$
• $S$ is expected to be "dense" in $X$

Shape ⟶ Sample

continuous object Array of rgb pixels

Map Reconstruction

Let $G$ be the unknown map of a city.
• $G$ is an embedded graph
• $G$ has the shortest-path metric
• $S$ is the GPS locations of cars
• $S$ is reasonably close to $G$

Data ⟶ Shape

Vietoris-Rips at scale $\epsilon>0$
In a metric space $(M,d)$, each subset $A$ size $k$ with $diam_d(A)<\epsilon$ is a $(k-1)$-simplex.

Manifold Reconstruction

(Adams H. et al.)
small $\epsilon$ + dense sample
=
Rips complex is a good reconstruction for manifolds

Graph Reconstruction

small $\epsilon$ + dense sample trick
does not work
😢

The Reconstruction Library

• I call it Shape Reconstruction
• Language: JavaScript
• Platform: (modern) Web Browsers
• Hosted on Github

This Presentation

• The framework is called RevealJS
• Language: JavaScript
• Platform: (modern) Web Browsers
• Latex Support: MathJax
• Features: Multiplexing, Notes, Timer, Autoslide, and more.
The speaker will now accept Questions