Voronoi-based k-order neighbour relations for spatial analysis

Spatial neighbour relations are a very important concept in spatial information science. Neighbourhood information is indispensable for many operations in spatial information systems, and it is therefore significant to describe and acquire it in an efficient way. In this paper, the concept of k-order neighbours is developed and a Voronoi-based model is formed for this type of neighbours, resulting in the so-called Voronoi k-order neighbours. Several methods for the computation of k-order neighbours for various given conditions are developed. An application in contour analysis is illustrated, i.e. the generation of a contour tree.