Dot Pattern Processing Using Voronoi Polygons as Neighborhoods

Narendra Ahuja

Abstract

Voronoi polygons are used as neighborhoods of points in dot patterns. This approach is compared with the other available notions of neighborhood, including those involving fixed radius, k nearest neighbors and minimal spanning tree. It is argued that Voronoi polygons possess intuitively appealing characteristics expected from a notion of the neighborhood of a point. Applications of the proposed definition to several common tasks in dot pattern processing including clustering, perceptual boundary extraction, and matching have been outlined.