All closest neighbors are proper Delaunay edges generalized, and its application to parallel algorithms
Arne Maus, Jon Moen, Drange · 2010
In this paper we first prove that for any set points P in the plane, the closest neighbor b to any point p in P is a proper triangle edge bp in D(P), the Delaunay triangulation of P. We also generalize this result and prove that the j’th (second, third,..) closest neighbors bj to p are also edges pbj in D(P) if they satisfy simple tests on distances from a point. Even though we can find many of the edges in D(P) in this way by looking at close neighbors, we give a three point example showing that not all edges in D(P) will be found. For a random dataset we give results from test runs and a model that show that our method finds on the average 4 edges per point in D(P). Also, we prove that the Delaunay edges found in this way form a connected graph. We use these results to outline two new parallel, and potentially faster algorithms for finding D(P). We then report results from parallelizing one of these algorithms on a multicore CPU (MPU), which resulted in a significant speedup; and on a graphics card, a NVIDA GPU, where we experienced a speeddown. We explain this by discussing the NVIDA SIMT programming model, how it differs from the well-known SIMD model, and why a speeddown is obtained instead of a speedup. Finally, we comment on the k’th closest neighbors problem.