An adaptive spatial clustering algorithm based on delaunay triangulation

In this paper, an adaptive spatial clustering algorithm based on Delaunay triangulation (ASCDT for short) is proposed. The ASCDT algorithm employs both statistical features of the edges of Delaunay triangulation and a novel spatial proximity definition based upon Delaunay triangulation to detect spatial clusters. Normally, this algorithm can automatically discover clusters of complicated shapes, and non-homogeneous densities in a spatial database, without the need to set parameters or prior knowledge. The user can also modify the parameter to fit with special applications. In addition, the algorithm is robust to noise. Experiments on both simulated and real-world spatial databases (i.e. an earthquake dataset in China) are utilized to demonstrate the effectiveness and advantages of the ASCDT algorithm.

Research highlights► An adaptive spatial clustering algorithm is developed for geo-referenced 2-D point data. ► To detect accurate clusters in a spatial database, global and local effects are considered through a hierarchical strategy. ► Based on the global and local criteria abstracted from the Delaunay triangulation, our ASCDT algorithm can automatically discover spatial clusters with extremely complex structures effectively and efficiently.