Abstract:
In this paper we first prove that for any set of 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) can be found in this way. 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 parallel algorithms for finding D(P). Finally, we comment on using these theorems and solving the k'th closest neighbors problem.
