The main aim of the IsoDen method is to improve on FOF by identifying halos over a wide range of densities, thereby exploiting the full dynamic range available in the data. The motivation is similar to that of the DENMAX algorithm [3, 6], but the procedure is substantially different. Another related method is presented in [15], but it is restricted to spherical isodensity surfaces. In some respects IsoDen corresponds to applying the FOF method at a range of densities or linking lengths, a course suggested by [5], but in an integrated and consistent way.

The idea of IsoDen is to actually calculate a spatial density field defined by the particles, and then identify halo centers as local peaks in this field. Isodensity surfaces are grown around each center, to find those particles belonging to each peak. When the isodensity surfaces of different centers touch, a new composite halo and isodensity surface is created that encompasses the two constituent peaks. In order for the method to work, the density field derived from the particle distribution must be reasonably smooth, so that the interpretation of the method in terms of isodensity surfaces is valid.

The density at each particle, , (*i* ranging from 1 to *N*),
is calculated as the sum of the masses, , of the nearest
particles, divided by the volume of the sphere enclosing those particles.
This is simply k-nearest neighbor density estimation
with [11].

where is the distance from particle *i* to
its nearest neighbor and the sum is over the nearest
neighbors of particle *i*.
The variable smoothing scale implicit in nearest neighbor estimation
is important because of the large
range in densities present in the simulations.
By using the nearest neighbor method
with, e.g., , the local resolution in the
density is tailored to the actual resolution available.

In principle the IsoDen method could use alternative density measures which satisfy the requirement of spatial continuity. One possibility is the phase space density: the mass per spatial volume element per velocity volume element. This may be advantageous for cosmology simulations, because low density halos generally have small internal velocities, (e.g., see Figures 1 to 4) and hence have similar phase space densities as halos with higher spatial density. Other density estimation techniques are also viable, c.f. [10], and may be more appropriate in other problem domains. We have experimented with the generalized nearest-neighbor technique [11] but find that for the same level of uncertainty in the density field, it is more computationally expensive.

The isodensity surfaces are defined implicitly by a graph-connectivity criterion similar to that used in FOF. Each particle is implicitly linked to nearest neighbors, where is a parameter of the method. An isodensity surface is defined by taking all the particles above some fixed density that are also linked together, as in FOF. The value of should be large enough that all particles are linked together when all particles are considered, i.e., the isodensity surface at zero density should comprise the entire system. should not be unnecessarily large, since this would compromise the spatial resolution of the method. In practice values of 12 to 24 have been successfully used. Note that isodensity surfaces are not directly calculated in the method (which is explained algorithmically below), but rather are a useful concept for understanding the method.

Once densities and linking lengths have been calculated, the particles are sorted by density, and then considered in order from highest density to lowest. Our goal is to assign each particle to a halo, which are numbered sequentially from zero. The halo number for each particle is calculated based on the halo numbers of the higher density particles to which it is linked, as follows:

- If the particle under consideration is not linked to any other particles with higher density, then a new halo is created and the particle is assigned to it.
- If the higher-density linked particles all belong to the same halo, then the new particle is assigned to that halo as well.
- Otherwise, the linked particles with higher density
belong to two or more distinct
halos.
In this case the pre-existing halos
*overlap*at the density of the particle being considered. A new composite halo is generated to represent the overlap of those halos. The membership lists of the overlapping halos are recorded, and then all the particles in the overlapping halos, along with the particle under consideration, are reassigned to the new composite halo.

Sat Sep 27 18:44:36 PDT 1997