Solid-angle based nearest-neighbor algorithm adapted for systems with low coordination number

In the invisible world of atoms and molecules, the way particles arrange themselves dictates the material's character. Whether a substance is a hard diamond, a slippery lubricant, or a flowing liquid depends entirely on the local neighborhood of its constituent parts. To understand these materials, scientists must first answer a deceptively simple question: who is a neighbor? In a dense crowd of particles, it is not always obvious which ones are touching and which are merely passing by. This distinction is crucial because the number of immediate neighbors a particle has, known as its coordination number, determines the structure of the entire system. For decades, researchers have relied on mathematical tools to draw these invisible boundaries, but these tools have struggled when the crowd is sparse or the arrangement is unusual, often misidentifying distant particles as close friends.

A team of researchers from Utrecht University and the Université Paris-Saclay has developed a refined method to solve this specific problem. They focused on an existing technique called the solid-angle-based nearest-neighbor algorithm, which determines neighbors by checking how much of a particle's surrounding view is blocked by its companions. While this method works well in dense, chaotic systems, it tends to make a systematic error in open, structured lattices where particles are few and far between. In these low-density environments, the original algorithm often reaches too far, counting particles that belong to the next layer of neighbors as if they were part of the first circle. The researchers introduced a geometric correction to fix this overcounting without adding any new adjustable settings to the calculation. Their modified approach, which they call mSANN, successfully identifies the correct number of neighbors in complex structures ranging from honeycomb patterns to diamond crystals, offering a more accurate map of the microscopic world.

The core challenge in identifying neighbors lies in the lack of a single, universal definition for what constitutes a "touch." In a perfect crystal, the answer is clear, but in real materials, thermal energy causes particles to jiggle, blurring the lines between layers. Traditional methods often rely on a fixed distance cutoff, drawing a circle around a particle and counting everyone inside. However, this fails when density changes across the material. Another popular method uses a geometric partitioning of space, dividing the area around each particle into a unique cell. While this avoids arbitrary distance limits, it is sensitive to tiny vibrations and can incorrectly include distant particles in low-coordination structures, such as a honeycomb lattice where each particle has only three neighbors. The solid-angle method was designed to be a robust alternative that requires no fixed distance settings. It works by imagining a sphere around a central particle and calculating the angular space each potential neighbor occupies. The algorithm expands the boundary until the neighbors collectively fill the entire sphere. This works beautifully in dense systems, but in open lattices, the geometry of the situation tricks the algorithm.

The researchers discovered that in open structures, the original method effectively draws a circle that is too large. Imagine a particle sitting at the center of a triangle formed by its three nearest neighbors. To fill the space around the center particle, the algorithm calculates a radius that reaches the corners of that triangle. In doing so, it inadvertently includes particles that sit just outside the triangle, in the next layer of the structure. This happens because the algorithm treats the space as if it needs to be filled by a circle passing through the neighbors, rather than a circle that simply contains them. This geometric oversight leads to a consistent overestimation of the number of neighbors, confusing the first layer of neighbors with the second.

To correct this, the authors proposed a simple geometric adjustment based on the relationship between the circle that passes through the neighbors and the circle that fits inside the shape they form. They realized that while the original method uses the outer circle, a more accurate approach for these sparse structures would be to use a radius that sits somewhere between the inner and outer limits. They introduced a modification that scales the calculated radius down, effectively shrinking the boundary just enough to exclude the distant particles while still allowing for the natural jiggling of atoms. This adjustment is purely geometric and requires no new parameters or tuning, preserving the original method's simplicity. It acts as a filter that prevents the algorithm from reaching too far in open lattices while remaining flexible enough to handle the thermal noise present in real materials.

The team tested their new method, mSANN, against the original algorithm and the traditional geometric partitioning method across a wide variety of simulated systems. In two-dimensional simulations of honeycomb and square lattices, the original methods frequently misidentified the number of neighbors, often counting six or five instead of the correct three or four. The modified method, however, consistently identified the exact coordination number for every particle, producing a sharp, clear distribution that matched the theoretical structure. In three-dimensional tests involving diamond and graphite structures, which also have low coordination numbers, the original methods again struggled to distinguish between the first and second layers of neighbors. The mSANN correction successfully resolved this, identifying the correct number of neighbors in all tested crystal types, including the simple cubic and body-centered cubic lattices.

The researchers also examined more complex, disordered systems, such as quasicrystals, which contain a mix of different shapes and neighbor counts. In these heterogeneous environments, the original solid-angle method sometimes created false connections across the diagonals of square-shaped gaps, effectively merging separate regions. The modified algorithm avoided these spurious links, preserving the true topology of the structure. Furthermore, in systems where different phases coexist, such as a boundary between a crystal and a disordered region, the new method provided a consistent identification of neighbors across the interface, whereas the other methods showed significant inconsistencies. This robustness suggests that the modification is particularly valuable for studying materials that are not perfectly ordered, where the local environment varies significantly from point to point.

Beyond accuracy, the researchers were concerned with the speed of the calculation, as neighbor identification is a fundamental step in many large-scale simulations. They implemented their algorithm in a way that leverages modern computing power, using parallel processing to handle the calculations efficiently. Their benchmarks showed that for small systems with fewer than a thousand particles, the traditional geometric method remains the fastest option. However, as the system size grows, the modified algorithm becomes significantly faster, outperforming the traditional method by nearly double in speed for very large systems containing millions of particles. This efficiency, combined with the improved accuracy in low-density environments, makes the new method a powerful tool for analyzing complex materials.

The work demonstrates that a careful look at the underlying geometry of a problem can lead to significant improvements in how we model the physical world. By recognizing that the original method's definition of a neighbor was too permissive in open structures, the researchers were able to introduce a correction that is both mathematically elegant and practically effective. The modified algorithm does not just fix a specific error; it provides a more reliable way to map the local structure of matter, from the rigid lattices of crystals to the fluctuating arrangements of disordered phases. For scientists studying the behavior of materials at the atomic scale, having a tool that can accurately count neighbors without getting confused by the gaps between them is a crucial step toward understanding the properties of the materials that make up our world.