The set of all points closest to a given point in a point set than to all other points in the set is an interesting spatial structure called a Voronoi Polygon for the point. The union of all the Voronoi polygons for a point set is called Voronoi Tessellation.

Many applications have been found based on the neighbourhood information provided by this tessellation. The dual of Voronoi tessellation is Delaunay Tessellation, also referred to as Delaunay Triangulation or Triangulated Irregular Network (TIN), which are lines drawn between points where their Voronoi polygons have an edge in common.

Delaunay tessellation is the most fundamental neighbourhood structure because many other important neighbourhood structures, such as, Gabriel Graph, Relative Neighbourhood Graph and Minimal Spanning Tree, can be derived from it.