Influence-based Voronoi diagrams of clusters

In this paper, we study a generalization of Voronoi diagram, called the Influence-based Voronoi Diagram (IVD). The input consists of a point set P in R^d, a collection C={C₁,C₂,…,C_n} where each C_i⊆P, i=1,2,…,n, is a cluster of points of P, and an influence function F(C,q) measuring the influence from a set C of points to any point q in R^d, and the goal is to construct an influence-based Voronoi diagram for C. By making use of a recent work called the Clustering Induced Voronoi Diagram (CIVD) for unclustered points, we are able to show that it is possible to utilize CIVD's space-partition ability and combine it with a divide-and-conquer algorithm to simultaneously resolve the space partition and assignment problems for a large class of influence functions. This overcomes a major difficulty of CIVD on the assignment problem. Our technique yields a (1−ϵ)-approximate IVD with size O(Nlog⁡N) in O(T₂(N)Nlog²⁡N+T₁(N)) time, where N is the total cardinalities of clusters in C, ϵ>0 is a small constant, and T₁ and T₂ are functions measuring how efficiently F(C,q) can be evaluated.