Various graph theoretic definitions of neighborhood have been used in the past in computer vision and clustering applications. In this paper we study the properties of a set of four related closest-point graphs using Monte Carlo methods: (i) the Delaunay triangulation (DT) and its dual, Voronoi tessellation, (ii) Gabriel graph (GG), (iii) the relative neighborhood graph (RNG), and (iv) the minimum spanning tree (MST). We examine the suitability of these graphs in the detection of structure in noisy images using Hough transform. We also explore each graph's structural stability under random positional noise. Delaunay triangulation is shown to be least sensitive to such noisy conditions.
Keywords: Voronoi tessellation, Delaunay triangulation, minimum spanning tree, relative neighborhood graph, Gabriel graph, closest-point graph, Hough transform, perceptual grouping, computer vision.