# Approximate Triangulations of Grassmann Manifolds
## 2 Materials and Methods
### Vietoris-Rips and Witness Complexes  
Now suppose we are given a discrete set \(X\) of points in some metric space (typically a Euclidean space \(\mathbb{R}^{m}\)). The standard example of such an object is a sample of points from some geometric object \(M\). We would like to recover information about \(M\) from the sample \(X\), and the first step is to obtain an approximation of \(M\) using only the point cloud \(X\). There are many such techniques; perhaps the most classical is the _Delaunay triangulation_ of \(X\). This is defined as follows. Say \(X=\{x_{1},x_{2},\ldots,x_{r}\}\subset\mathbb{R}^{m}\). The _Voronoi decomposition_ of \(\mathbb{R}^{m}\) relative to \(X\) is the partition of \(\mathbb{R}^{m}\) into cells \(V(x_{i})\), \(i=1,\ldots,r\), defined by  
\[V(x_{i})=\{x\in\mathbb{R}^{m}:||x-x_{i}||\leq||x-x_{j}||,j\
eq i\}.\]  
The corresponding Delaunay triangulation, \(\operatorname{Del}(X)\), is the nerve of the Voronoi decomposition; that is, a collection \(V(x_{i_{0}}),\ldots,V(x_{i_{\ell}})\) forms an \(\ell\)-simplex in \(\operatorname{Del}(X)\) if \(\cap_{j=0}^{\ell}V(x_{i_{j}})\
eq\emptyset\). One obtains a geometric realization of \(\operatorname{Del}(X)\) via the map \(V(x_{i})\mapsto x_{i}\). See Figure 2 for an example. While the Delaunay triangulation provides a good approximation to the underlying space \(M\), it has several disadvantages. If the point cloud \(X\) is large, there will be a very large number of simplices in \(\operatorname{Del}(X)\). In addition, \(\operatorname{Del}(X)\) suffers from the \"curse of dimensionality;\" that is, if the ambient dimension (\(m\)) is large, calculating the Voronoi decomposition is computationally expensive. There are many popular alternatives to the Delaunay triangulation. The one used most often is the _Vietoris-Rips complex_, which is built as follows. Consider the point cloud \(X\) and let \(r>0\). The Vietoris-Rips complex with parameter \(r\) is the simplicial complex \(VR(X,r)\) whose \(k\)-simplices are  
\[\{(x_{0},\ldots,x_{k}):d(x_{i},x_{j})<r,i\
eq j\}.\]  
That is, if one imagines a ball of radius \(r/2\) around each point \(x\in X\), then we join the points \(x_{i}\) and \(x_{j}\) with an edge if the balls intersect. Observe that if \(r<r^{\prime}\) then there is an inclusion of complexes \(VR(X,r)\subset VR(X,r^{\prime})\). We therefore have a nested sequence of complexes \(\{VR(X,r)\}_{r\geq 0}\) and we may study the persistent homology of this filtration. The corresponding barcodes yield information about the topology of the underlying space \(M\). Many software packages support the calculation of Vietoris-Rips persistence on point clouds. In this paper, we use the Eirene package developed by [PERSON] [8]. Other popular programs include [PERSON]'s Ripser [9] and [PERSON]'s Perseus [10]. In Section 3.5, we shall use the _witness complexes_ of [PERSON] and [PERSON] [11]. The idea is to model the Delaunay triangulation on a smaller set of points \(L\subset X\), called _landmarks_, in such a way that the topology of the underlying object is well-approximated. Moreover, the definition makes sense  
Figure 2: (**a**) a Delaunay triangulation of a collection of points in the plane with the corresponding Voronoi diagram, and (**b**) two associated witness complexes. in any metric space, so assume that \(X\) is a metric space with distance function \(d\) (e.g., \(X\) could be a finite point cloud in \(\mathbb{R}^{m}\) with the usual Euclidean distance). Choose a subset \(L=\{\ell_{1},\ell_{2},\ldots,\ell_{n}\}\) of \(X=\{x_{1},x_{2},\ldots,x_{N}\}\) and let \(R\geq 0\) be a real number. The _witness complex_\(W(X,L,R)\) is defined as follows:  
* The vertex set of \(W(X,L,R)\) is \(L\);
* \(\ell,\ell^{\prime}\in L\) span an edge if there exists an \(x\in X\), called a _witness_, such that \[d(x,\ell),d(x,\ell^{\prime})\leq R+\min\{d(x,\ell^{\prime\prime}):\ell^{\prime \prime}\in L-\{\ell,\ell^{\prime}\}\};\]
* A collection \(\ell_{0},\ldots,\ell_{p}\in L\) spans a \(p\)-simplex if \(\{\ell_{i},\ell_{j}\}\) span an edge for all \(i\
eq j\).