Void Identification Algorithm

We identify voids using a substantially modified version of the parameter-free void finder ZOBOV (Neyrinck 2008; Lavaux & Wandelt 2011) called VIDE (Void IDentification and Examination). You can download VIDE and use it for free:

Code website (bitbucket)
Other versions:

Our void-finding method is based on a Voronoi tessellation of the tracer particles (in this case, galaxies) to estimate the density field (van de Weygaert 2007; Platen et al. 2011) followed by a watershed algorithm to group Voronoi cells into zones and subsequently voids (Platen et al. 2007). The algorithm works as follows:
  • We build a Delaunay tessellation of the volume from the tracer positions in redshift coordinates.
  • We assign a density to each galaxy based on its Voronoi volume.
  • Using this estimated density ZOBOV executes a procedure similar to the Watershed algorithm: the entire volume is split into “zones”, with each zone corresponding to the attraction basin of a local minimum of the density field. 
  • ZOBOV then assigns a core density to each zone that corresponds to the lowest local minimum and assembles these zones into voids by successively joining pairs of zones if they share the lowest common saddle point in the density field.
This approach is related to the theory of persistence brought to the field of large scale structures by Sousbie (2011). There are no parameters that control the density determination, the construction of zones, their evolution into voids, or indeed any portion of this algorithm. Under this framework a “void” is a collection of zones that share common saddle points; walls, filaments, and clusters naturally divide a given volume into these voids. The volume of the void is defined as the sum of the Voronoi volumes of its zones. We may record these voids either by their geometrical definition (e.g., a collection of Voronoi cells) or by the tracers contained within them.

There is a natural ordering between voids: a void V1 is a sub-void of another void V2 if V2 has a larger number of zones than V1 and all zones of V1 are in V2. We can use this property to build a tree of voids. The tree is built in this order:
  • We build a list of voids attached to each existing zone
  • For each void, we look up the parent void for each void by
    • taking one of the zones of the considered void and look at all voids which are attached to it
    • choosing the parent void such that its set of zones is a strict superset of the considered void, and at the same the smallest of all voids in the list

This tree allows the construction of a stack where double counting of the same volume element is prohibited.

Here on the left, we give an illustration of voids identified in a slice of an N-body simulation. The tree depth where each void belongs is indicated by the color. Because the voids are represented using the convex envelope of the points lying in the slice, there are some overlaps between the shapes. It is nonetheless clear that voids are sorted hierarchically. The one in the lowest depth being the biggest, and the one in the highest depth the smallest.