An Algorithm for Self-adaptive Partition of Scattered Points in Planar Domain

This paper presents a method to partition the scattered points in planar domain based on grid-statistics and adaptive binary-partition.The basic idea of the method is as follows.First,build a grid field which can cover over all planar points to create the spatial index of the points.Then,figure out the position of every point in the grid field,such as the row and column place in the field,meanwhile,reserve the number of points in each grid.Finally,set the number of iterations as the parameter of terminating to partition the scattered points with proposed rules.This method can divide the data point-set into several groups flexibly and the result is relatively balanced.Besides,the computational efficient of the algorithm is relatively high and not too much extra storage space is needed.The method proposed in this paper can be used in the existing spatial analysis algorithms using partitioning-strategy and can be further applied to the related parallel algorithms.It also provides reference for adaptive partition of other types of spatial elements.