Fixed-radius Near Neighbors Searching for 2D Simulations on the GPU using Delaunay Triangulations

Abstract

We propose to explore a GPU solution to the fixed-radius nearest-neighbor problem in 2D based on Delaunay triangulations. This problem is crucial for many particle-based simulation techniques for collision detection or momentum exchange between particles. Our method computes the neighborhood of each particle at each iteration without neighbor lists or grids, using a Delaunay triangulation whose consistency is preserved by edge flipping. We study how this approach compares to a grid-based implementation on a flocking simulation with variable parameters.