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


Road ⟶ GPS locations

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

🤔