^{1}, Laura Filion

^{2}, Chantal Valeriani

^{3}and Daan Frenkel

^{2}

### Abstract

We propose a parameter-free algorithm for the identification of nearest neighbors. The algorithm is very easy to use and has a number of advantages over existing algorithms to identify nearest-neighbors. This solid-angle based nearest-neighbor algorithm (SANN) attributes to each possible neighbor a solid angle and determines the cutoff radius by the requirement that the sum of the solid angles is 4π. The algorithm can be used to analyze 3D images, both from experiments as well as theory, and as the algorithm has a low computational cost, it can also be used “on the fly” in simulations. In this paper, we describe the SANN algorithm, discuss its properties, and compare it to both a fixed-distance cutoff algorithm and to a Voronoi construction by analyzing its behavior in bulk phases of systems of carbon atoms, Lennard-Jones particles and hard spheres as well as in Lennard-Jones systems with liquid-crystal and liquid-vapor interfaces.

The authors thank K. Shundyak for fruitful discussions. The work of J.vM. at the FOM Institute is part of the research program of FOM and is made possible by financial support from the Netherlands Organization for Scientific Research (NWO). D.F. acknowledges financial support from the Royal Society of London (Wolfson Merit Award) and from the ERC (Advanced Grant agreement 227758). C.V. acknowledges support from an Individual Marie Curie Fellowship (in Edinburgh) and from a Juan de la Cierva Fellowship (in Madrid). L.F. acknowledges support from the EPSRC, UK for funding (Programme Grant EP/I001352/1).

I. INTRODUCTION

II. METHOD

A. Description of SANN method

B. Algorithm

C. Algorithm properties

III. SIMULATION DETAILS

A. Sample preparation

B. Voronoi and SANN implementation details

C. Bond-order correlator

IV. RESULTS

A. Bulk phases

B. Interfaces

C. Application to bond-order parameters

D. Benchmarking

V. CONCLUSION

### Key Topics

- Liquid crystals
- 24.0
- Carbon
- 22.0
- Graphite
- 17.0
- Gas liquid interfaces
- 14.0
- Diamond
- 11.0

##### C09K19/00

## Figures

Definition of the angle θ_{ i, j } associated with a neighbor *j* of particle *i*. Here, *r* _{ i, j } is the distance between both particles and is the neighbor shell radius.

Definition of the angle θ_{ i, j } associated with a neighbor *j* of particle *i*. Here, *r* _{ i, j } is the distance between both particles and is the neighbor shell radius.

2D comparison of the SANN and Voronoi algorithms. In all three panels we show a central particle with potential nearest neighbors A through F. In panel (a) we sketch the SANN algorithm: the green circle shows the shell radius, and particles B through F are identified as nearest neighbors. Note that in all panels the nearest neighbors are indicated with red lines. To facilitate the comparison between a Voronoi construction and the SANN algorithm, in panel (b) we make use of the fact that the SANN algorithm is scale free, i.e., = where 0.5*r* _{ i, j } is simply the distance from particle *i* to the midpoint between *i* and *j*, and is half the shell radius. In panel (b) the green circles have a radius equal to the half the shell radius of the center particle, and are centered around each particle; the black lines are constructed by finding the intersection of the green circles and indicate the width of the solid angle between the center particle and each of its neighbors, respectively. Finally, in panel (c) we show a Voronoi construction for the same set of particles. Note that the Voronoi construction finds an extra nearest neighbor, i.e., particle A.

2D comparison of the SANN and Voronoi algorithms. In all three panels we show a central particle with potential nearest neighbors A through F. In panel (a) we sketch the SANN algorithm: the green circle shows the shell radius, and particles B through F are identified as nearest neighbors. Note that in all panels the nearest neighbors are indicated with red lines. To facilitate the comparison between a Voronoi construction and the SANN algorithm, in panel (b) we make use of the fact that the SANN algorithm is scale free, i.e., = where 0.5*r* _{ i, j } is simply the distance from particle *i* to the midpoint between *i* and *j*, and is half the shell radius. In panel (b) the green circles have a radius equal to the half the shell radius of the center particle, and are centered around each particle; the black lines are constructed by finding the intersection of the green circles and indicate the width of the solid angle between the center particle and each of its neighbors, respectively. Finally, in panel (c) we show a Voronoi construction for the same set of particles. Note that the Voronoi construction finds an extra nearest neighbor, i.e., particle A.

Nearest neighbors distribution *P*(*N* _{ n }) for a Lennard-Jones liquid (panel a) and fcc crystal (panel b) obtained by fixed-distance cutoff (*C*), Voronoi construction (*V*) and SANN considering neighbors belonging to the first coordination shell (*S*). Panels (c) and (d) plot the pair correlation functions *g*(*r*), considering all particles, as a reference (thin grey dotted line), and *g* _{ nn }(*r*), considering only nearest neighbors (Voronoi (*V*) and SANN (*S*)) and next-nearest neighbors (SANN (*S* _{2})), for both the liquid (c) and the fcc crystal (d). In addition, their fraction *g* _{ nn }(*r*)/*g*(*r*) is shown.

Nearest neighbors distribution *P*(*N* _{ n }) for a Lennard-Jones liquid (panel a) and fcc crystal (panel b) obtained by fixed-distance cutoff (*C*), Voronoi construction (*V*) and SANN considering neighbors belonging to the first coordination shell (*S*). Panels (c) and (d) plot the pair correlation functions *g*(*r*), considering all particles, as a reference (thin grey dotted line), and *g* _{ nn }(*r*), considering only nearest neighbors (Voronoi (*V*) and SANN (*S*)) and next-nearest neighbors (SANN (*S* _{2})), for both the liquid (c) and the fcc crystal (d). In addition, their fraction *g* _{ nn }(*r*)/*g*(*r*) is shown.

Nearest-neighbor distribution and *g*(*r*) as in Figure 3, but for a monodisperse hard spheres system at ϕ = 0.54 (panels a and c) and ϕ = 0.61 (panels b and d).

Nearest-neighbor distribution and *g*(*r*) as in Figure 3, but for a monodisperse hard spheres system at ϕ = 0.54 (panels a and c) and ϕ = 0.61 (panels b and d).

Nearest-neighbor distribution and *g*(*r*) as in Figure 3, but for both a 3-fold coordinated carbon liquid (panels a and c) and graphite crystal (panels b and d).

Nearest-neighbor distribution and *g*(*r*) as in Figure 3, but for both a 3-fold coordinated carbon liquid (panels a and c) and graphite crystal (panels b and d).

Nearest-neighbor distribution and *g*(*r*) as in Figure 3, but for both a 4-fold coordinated carbon liquid (panels a and c) and diamond crystal (panels b and d).

Nearest-neighbor distribution and *g*(*r*) as in Figure 3, but for both a 4-fold coordinated carbon liquid (panels a and c) and diamond crystal (panels b and d).

Simulation snapshot of 3-fold coordinated carbon graphite showing the first neighbors (yellow) of a center particle (gray). Surrounding particles that are not part of the neighborhood are shown in blue. (a) Voronoi construction; (b) SANN algorithm; and (c) Top-view on the center layer of panel b.

Simulation snapshot of 3-fold coordinated carbon graphite showing the first neighbors (yellow) of a center particle (gray). Surrounding particles that are not part of the neighborhood are shown in blue. (a) Voronoi construction; (b) SANN algorithm; and (c) Top-view on the center layer of panel b.

Results for two-phase samples in a slab-geometry, with the two interfaces oriented normal to the *x*-direction. The two phases are (a) liquid-crystal and (b) liquid-vapor. Note that the densities of the liquid in both the cases are not same. For both samples the upper panel shows, as function of *x*-position, the average number of nearest neighbors, ⟨*N* _{ Nb }(*x*)⟩, and the lower panel the corresponding variance, , for each of the algorithms: fixed-distance cutoff (*C*) with *r* _{ c } = 1.5, Voronoi construction (*V*) and SANN considering neighbors belonging to the first coordination shell (*S*). Note the different scales on the y axis.

Results for two-phase samples in a slab-geometry, with the two interfaces oriented normal to the *x*-direction. The two phases are (a) liquid-crystal and (b) liquid-vapor. Note that the densities of the liquid in both the cases are not same. For both samples the upper panel shows, as function of *x*-position, the average number of nearest neighbors, ⟨*N* _{ Nb }(*x*)⟩, and the lower panel the corresponding variance, , for each of the algorithms: fixed-distance cutoff (*C*) with *r* _{ c } = 1.5, Voronoi construction (*V*) and SANN considering neighbors belonging to the first coordination shell (*S*). Note the different scales on the y axis.

Visual representation of the three algorithms in a two-phase liquid-vapor Lennard-Jones system: fixed-distance cutoff (top), Voronoi construction (center) and SANN (bottom). In each case, we select the same particles and check which neighbors are detected using each algorithm.

Visual representation of the three algorithms in a two-phase liquid-vapor Lennard-Jones system: fixed-distance cutoff (top), Voronoi construction (center) and SANN (bottom). In each case, we select the same particles and check which neighbors are detected using each algorithm.

Distribution of the local bond-order correlator *d* _{6}(*i*, *j*) using different neighbor criteria. Panel (a) shows results for Lennard-Jones fcc crystal (upper panel) and liquid phases (lower panel), panel (b) for the 3-fold coordinated carbon graphite (upper panel) and liquid (lower panel) phases, and panel (c) for the 4-fold coordinated carbon diamond (upper panel) and liquid (lower panel) phases. For the carbon phases the fixed-distance cutoff distance was set to 2.7 to include the next-nearest neighbors, as do inherently both the Voronoi and SANN algorithms.

Distribution of the local bond-order correlator *d* _{6}(*i*, *j*) using different neighbor criteria. Panel (a) shows results for Lennard-Jones fcc crystal (upper panel) and liquid phases (lower panel), panel (b) for the 3-fold coordinated carbon graphite (upper panel) and liquid (lower panel) phases, and panel (c) for the 4-fold coordinated carbon diamond (upper panel) and liquid (lower panel) phases. For the carbon phases the fixed-distance cutoff distance was set to 2.7 to include the next-nearest neighbors, as do inherently both the Voronoi and SANN algorithms.

## Tables

Run-times in milliseconds of the fixed-distance cutoff (C), the Voronoi construction (V) and the SANN algorithm (S), and their ratios V/C and S/C. For details on the system samples we refer to Sec. III A, for implementation details to Sec. III B, and for the benchmarking procedure to the main text.

Run-times in milliseconds of the fixed-distance cutoff (C), the Voronoi construction (V) and the SANN algorithm (S), and their ratios V/C and S/C. For details on the system samples we refer to Sec. III A, for implementation details to Sec. III B, and for the benchmarking procedure to the main text.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content