This is part of a (planned) multi-part tutorial series demonstrating both the utility and generality of the *Mapper* method. This vignette describes how one might use the *Mapper* method to **compare shapes**.

One of the central preoccupations of computer vision is understanding how to recognize objects representing semantically ‘equivalent’ things. In particular, much work has been done on *quantifying* notions of equivalence between shapes in both *robust* and *meaningful* ways. Generally speaking, to formally ascertain whether certain shapes represent the ‘same’ object, it’s necessary to first equip these shapes with some kind of geometric structure. For example, if the object comes in the form of point cloud data, a typical approach is to equip these shapes with a distance metric and view them as *metric spaces*.

Recall that a metric space is a pair \((d, X)\) where \(X\) is a set equipped with a function \(d: X \times X \to \mathbb{R}\) which expresses the some measure of distance between points. To qualify as a true metric, for any points \(x, x', x'' \in X\), \(d\) must satisfy:

- \(d(x, x') \geq 0, d(x, x') = 0\) iff \(x = x'\) (non-negativity, identity)
- \(d(x, x') = d(x', x)\) (symmetry)
- \(d(x, x') + d(x', x'') \geq d(x, x'')\) (triangle-equality)

The conditions satisfied by a metric express intuitive notions of distance in an element-wise manner. However, if one wishes to compare *groups* of elements, a convenient and natural extension to a metric is the *Hausdorff distance*.

The Hausdorff distance measures how far apart *subsets* of a metric space are from each other; that is, given two non-empty subsets \(X, Y\) of some common metric space \((Z, d_Z)\), it expresses the maximum distance a set is from the nearest point in the other set. The typical definition of the ‘directed’ Hausdorff distance is:

\[\begin{equation}\tag{1} d_{DH}(X, Y) = \sup_{x \in X}\inf_{y \in Y} d_Z(x, y) \end{equation}\]

The above distance is not symmetric (hence the ‘directed’ designation) and extension to \(d_Z\) does not result in a not a true metric. We can generalize \(d_{DH}\) by taking the maximum directed Hausdorff distance between \(X\) and \(Y\) and \(Y\) and \(X\):

\[\begin{equation}\tag{2} d_{H}(X, Y) = \max \{ \, d_{DH}(X,Y), \,d_{DH}(Y,X) \, \} \end{equation}\]

It can be shown that this symmetric Hausdorff distance *is* in fact a metric on the space of compact subsets of \(Z\). This nice property of the Hausdorff distance enables a convenient and natural extension of any metric \(d_Z\) to be defined between subsets of \(Z\).

Intuitively, the Hausdorff distance provides very convenient distance measure for the *mapper* construction. Since each node in a *mapper* represents a subset of the data, if the space the *mapper* nodes were constructed on was a metric space, the Hausdorff distance can be used to *embed* the *mapper* into a metric space.

To illustrate this idea, I’m going to borrow some high-fidelity pose data sets from this source

```
target_dir <- tempdir()
target_file <- file.path(target_dir, "elephant-poses.tgz")
pose_db <- "http://people.csail.mit.edu/sumner/research/deftransfer/data"
if (!file.exists(target_file)){
download.file(file.path(pose_db, "elephant-poses.tgz"), destfile = target_file)
if (!dir.exists(file.path(target_dir, "elephant-poses"))){
untar(tarfile = target_file, exdir = target_dir)
}
}
```

As evident from the name of the file, the set of poses downloaded above are meshes of an elephant in different running poses. Here I’ll use the readobj and rgl packages to view what the meshes look like.

```
library("readobj")
el_ref_fn <- normalizePath(file.path(target_dir, "elephant-poses", "elephant-reference.obj"))
el_ref <- readobj::read.obj(el_ref_fn)
shade3d(readobj::tinyobj2shapelist3d(el_ref), color = "gray")
rglwidget()
```