Map segmentation for geospatial data mining through generalized higher-order Voronoi diagrams with sequential scan algorithms

Segmentation is one popular method for geospatial data mining. We propose efficient and effective sequential-scan algorithms for higher-order Voronoi diagram districting. We extend the distance transform algorithm to include complex primitives (point, line, and area), Minkowski metrics, different weights and obstacles for higher-order Voronoi diagrams. The algorithm implementation is explained along with efficiencies and error. Finally, a case study based on trade area modeling is described to demonstrate the advantages of our proposed algorithms.

► Propose a flexible sequential-scan based algorithm for higher-order Voronoi diagrams. ► The algorithm covers order-k Voronoi diagrams, ordered order-k Voronoi diagrams, and kth nearest Voronoi diagrams. ► The higher-order Voronoi algorithm works with other generalized settings such as weights, in the presence of obstacles, and complex data types. ► The algorithm is computationally efficient in O(F) time where F is the number of pixels. ► The algorithm is flexible and effective to be used with various environmental settings. ► Applications of the algorithm discovering geographic knowledge through web map segmentation.