Direct Algorithm for the Exact Voronoi Diagram on Discrete Topographic Space

  Objectives  Voronoi diagram is a fundamental structure in geo-computing, but it still encounters the problem of exactness and the challenge of an exact algorithm comparable to planar Voronoi diagrams in the topographic space.

  Methods  The geodesic distance field of computational geometry is introduced into the triangulated irregular network in the discrete topographic surface. The hyperbolic curves representing the bisector are gradually grown from the singularity of the distance field on the edge of the grid. The precise division of the discrete surface is obtained by the arrangement of the hyperbolic curves, and the exact geodesic Voronoi diagram (GVD) is obtained by clustering the divided patches. Then, the exact Voronoi diagrams are tested quantitatively and qualitatively.

  Results and Conclusions  It is found that the exact GVD can bring a basic improvement for the spatial analysis of topographic surface. The direct algorithm based on singular growth and hyperbolic arrangement is intuitive and easy to implement, which avoids the excessive subdivision and preprocessing of grid patches by the existing algorithms, and provides a useful exploration for the development of Voronoi diagram analysis in digital topographic analysis.