Are there "geometrically nice" sets from which to construct coverings that admit "Vietoris-Rips like" approximations to the nerve?

Question

It is well known that the nerve (or Čech complex) of a covering consisting of metric balls with a common fixed radius is nicely approximated by the Vietoris-Rips complex. Being a flag complex on its 1-simplices, the latter is computationally much more tractable than the nerve itself.

Does anybody know of other classes of sets that yield approximations to the nerve à la what Vietoris-Rips does for the case of balls? I'm quite open to vague answers, and "approximation" can here certainly mean much poorer ones than Vietoris-Rips.

Answer 1

Since the question is rather broad, the answer got unwieldy. Sorry, I hope some of this is relevant to the sort of questions you are asking.

Complexity of Approximating the Čech Complex

The computational tractability of the Vietoris-Rips complex is an engaging - but largely false - contemporary myth. While it is true that testing whether two balls intersect is much easier than testing for higher order intersection, the number of simplices in a Rips complex on $m$ vertices can vary wildly from $m$ for an edgeless $1$-skeleton to a staggering $2^m$ for the complete $1$-skeleton.

A more balanced approach is to build the Čech complex faithfully up to an $n$-skeleton for $n \geq 1$ and then construct the flag complex on top by inserting those higher simplices whose $n$-dimensional faces all exist. Clearly, the traditional Rips complex is the $n=1$ version of such an approximation scheme. At the cost of computing common intersections of $n+1$ balls, one can often drastically reduce the total number of simplices in the approximation-complex. In practice, even $n=2$ provides huge savings of memory over a traditional Rips complex.

Sandwiching of Filtrations

The important thing to note is that "interleaving" or "sandwiching" is an equivalence relation on one-parameter nested families of topological spaces (called filtrations). Consider two such filtrations $X = \lbrace X_a\rbrace_{a > 0}$ and $Y = \lbrace Y_b\rbrace_{b > 0}$. We say that $X$ and $Y$ are $d$-sandwiched for $d \geq 1$ if

$$ X_{a/d} \subset Y_a \subset X_{ad} $$

for each $a \in \mathbb{R}$. Clearly, the Rips and Čech filtrations built with the usual metric balls are $2$-sandwiched. More importantly, if $X$ and $Y$ are $d$-sandwiched, and $Y$ and $Z$ are $e$-sandwiched, then $X$ and $Z$ are $(de)$-sandwiched.

So, the situation is not too exciting in finite dimensional Euclidean space (where Rips and Čech complexes are often built) because all norms are equivalent. No matter which norm you might choose to build balls, there will be some sandwiching between Čech and Rips filtrations, or two different Rips filtrations, or... ? The point is, changing the norm to generate square-shaped balls (for instance) does not achieve too many interesting things in terms of sandwiching, but it might make checking for higher order intersections easier.

The situation is much more exciting in infinite dimensional space, but much less is known I think.

Replacing Balls Entirely

Let $P$ be a finite point set in a normed vector space $(V,\|\cdot\|)$. Let $U = \lbrace U_\epsilon \rbrace_{\epsilon > 0}$ be a filtration of subsets of $V$ all containing $0$, and consider the (filtered) nerve generated by the sets $p + U_\epsilon$ for $p \in P$. We will approximate this filtered nerve $C(U_\epsilon)$ using Rips complexes built out of generic sets (meaning: not necessarily balls).

Let $W = \lbrace W_\epsilon \rbrace_{\epsilon > 0}$ be any other filtration whose sets all contain $0$ and which is $d$-sandwiched with $U$ for some $d \geq 1$. That is, for each $\epsilon > 0$ we have

$$ U_{\epsilon/d} \subset W_\epsilon \subset U_{d\epsilon}.$$

Thus, the Cech filtrations $C(U_\epsilon)$ and $C(W_\epsilon)$ are $d$-sandwiched. But now: the Rips filtration $R(W_\epsilon)$ is $2$-sandwiched with $C(W_\epsilon)$, and hence $2d$-sandwiched with $C(U_\epsilon)$. So, as long as the sets you grow around your point cloud in the Cech and Rips complex have this sandwiching property, you will be able to extract an approximation theorem. In the case where the Cech complex is built using $L^2$-balls $B$, you can get a $2d$-approximation by using a Rips complex built with any sets $U_\epsilon$ so that

$$U_{\epsilon/d} \subset B_\epsilon \subset U_{d\epsilon}$$

for each $\epsilon > 0$.