Exact Voronoi diagram for topographic spatial analysis

Abstract

The Voronoi diagram (VD) is a fundamental geo-computing structure that has crucial applications. Computing this structure on a topographic surface requires having every point clustered on the geodesic distances, and thus the same challenging task as the geodesic distance mapping. This article proposes a new algorithm for the geodesic VD (GVD) by breaking up the highly complicated task into regular routines on the exact computation. The exact approach is due to the irregular rough nature of the Earth surface, where the discrete computation is more appropriate. The key operation involves a direct window growth devised to avoid the overloaded facet splitting and realized in a conic arrangement. Conventional clustering and GVD structure post-extraction are built on top of the window growth. The fundamental role of GVD in geo-computing is then demonstrated. The experimental results showed that the dual structure of GVD is useful in justifying the potential wrong triangulations from the popularly used 2D Delaunay, and the geometric exactness of GVD is more reliable in guaranteeing the surface process model efficiency and convergence, under the harsh checking of centroidal Voronoi tessellation optimization.

Keywords

• geodesic distance mapping
• geodesic voronoi diagram
• window growth
• conic arrangement
• delaunay triangulation
• centroidal voronoi tessellation