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$.

`well known'. The terms nerve and Cech comlex have a wider and older use than just this. The Wikipedia page is not to be trusted. Vietoris complex is also used in a wider and older meaning for an arbitrary covering. Looking at that Wikipedia entry there are numerous inaccuracies. The Cech complex is not dependent on the embedding. Secondly what do you mean by`

other classes of sets'? Have you investigated Dowker's paper on the homology of relations? – Tim Porter Mar 8 '13 at 9:50metric ballsand the corresponding VR complex. I also apologize for the vagueness of the phrase "other classes of sets". I simply meant "something playing the role of balls in the above-mentioned relationship between the VR complex and the nerve". – gspr Mar 8 '13 at 11:01