Vietoris–Rips Complex

The Vietoris-Rips Complex is a special type of simplicial complex built on a metric space. This topological concept has been around for a long time, although its invigoration in the twenty-first century was by the TDA community. The popularity of the complex is due to its increasing use in shape reconstruction; see [1,3] for example. The easy (but not always efficient) algorithmic approaches to compute the Vietoris-Rips complex of a finite metric space makes it more palatable choice over its close relative: the Čech complexes.

Definition

Given a metric space (M,d_M) and a scale \epsilon>0, the Vietoris-Rips complex R_{\epsilon}(M) is a simplicial complex such that \sigma=\{x_1,x_2,\ldots,x_n\}\in R_\epsilon(M) if and only if \{x_1,x_2,\ldots,x_n\}\subseteq M with diam(\sigma)\leq\epsilon.

Demo

We run a little JavaScript demo of Vietoris-Rips complex for a finite subset V under the Euclidean distance. Although the computed Rips complex is an abstract simplicial complex (without an embedding), we only show its shadow; see [2] for a definition.

tex`\epsilon=${scale}`

As we can see, the set V is currently empty, and the scale \epsilon is set to zero. We pick a set of points in the plain by clicking on the canvas below. A word of caution: picking more than 30 points can substantially slow down your browser!

V = [];

{
  const height = "300px";
  const container = d3.create("div").style("position", "relative");
  let svg = container
    .append("svg")
    .attr("class", "canvas")
    .style("margin-left", "15px")
    .style("width", "90%")
    .style("height", height)
    .style("border", "0.5px solid #eee");
  
  const triangles = svg.append("g").attr("class", "triangles");
  const edges = svg.append("g").attr("class", "edges");
  const vertices = svg.append("g").attr("class", "vertices");

  // scale
  container
    .append("div")
    .style("width", "15px")
    .style("height", height)
    .style("background", "#eee")
    .style("position", "absolute")
    .style("top", "0")
    .style("bottom", "0")
    .append("div")
    .style("width", "100%")
    .style("height", scale + "px")
    .style("background", "steelblue");
  container
    .append("div")
    .style("margin-left", "3px")
    .style("width", height)
    .style("display", "inline-block")
    .style("text-align", "center")
    .style("transform", "rotate(-90deg)")
    .style("transform-origin", "top left")
    .html(tex`\epsilon`.outerHTML);

  drawRips(svg, sc.rips(V, scale, 2));

  svg.on("click", (e) => {
    const coord = d3.pointer(e);
    V.push(coord);
    drawRips(svg, sc.rips(V, scale, 2));
  });
  return container.node();
}

We now use the slider to set the scale \epsilon:

viewof scale = Inputs.range([0, 300], {
  step: 1,
  value: 0,
  label: tex`\epsilon`
})

viewof btn = Inputs.button("clear", {
  value: null,
  reduce: () => { V.length = 0; viewof scale.value = 0;viewof scale.dispatchEvent(new CustomEvent("input")); }
})

As we add more points or fiddle with the scale, the Betti numbers of the computed Vietoris-Rips complex can also be computed.

import { slider } from "@jashkenas/inputs"

sc = require("https://cdn.jsdelivr.net/npm/@tdajs/simplicial-complex@1.2.1/dist/min.js")

drawRips = function (svg, rips) {
  if (rips.simplices[2]) {
    svg.selectAll(".triangle")
      .data(rips.simplices[2])
      .join("path")
      .attr("class", "triangle")
      .attr("d", (d) => d3.line()(d.map((v) => V[v])))
      .attr("fill", "lightgreen")
      .attr("stroke", "none")
      .attr("opacity", "0.5");
  }
  if (rips.simplices[1]) {
    svg.selectAll(".edge")
      .data(rips.simplices[1])
      .join("path")
      .attr("class", "edge")
      .attr("d", (d) => d3.line()(d.map((v) => V[v])))
      .attr("stroke", "red");
  }

  svg.selectAll(".vertex")
    .data(V)
    .join("circle")
    .attr("class", "vertex")
    .attr("class", "vertex")
    .attr("cx", (d) => d[0])
    .attr("cy", (d) => d[1])
    .attr("r", "2px")
    .on("mouseover", function () {
      d3.select(this).attr("fill", "orange").attr("r", "5px");
    })
    .on("mouseout", function () {
      d3.select(this).attr("fill", "black").attr("r", "2px");
    });
    return svg;
}