On Clustering Induced Voronoi Diagrams

In this paper, we study a generalization of the classical Voronoi diagram, called clustering induced Voronoi diagram (CIVD). Different from the traditional model, CIVD takes as its sites the power set U of an input set P of objects. For each subset C of P, CIVD uses an influence function F (C, q) to measure the total (or joint) influence of all objects in C on an arbitrary point q in the space Rᵈ, and determines the influence-based Voronoi cell in Rᵈ for C. This generalized model offers a number of new features (e. g. , simultaneous clustering and space partition) to Voronoi diagram which are useful in various new applications. We investigate the general conditions for the influence function which ensure the existence of a small-size (e. g. , nearly linear) approximate CIVD for a set P of n points in Rᵈ for some fixed d. To construct CIVD, we first present a standalone new technique, called approximate influence (AI) decomposition, for the general CIVD problem. With only O (n n) time, the AI decomposition partitions the space R^d into a nearly linear number of cells so that all points in each cell receive their approximate maximum influence from the same (possibly unknown) site (i. e. , a subset of P). Based on this technique, we develop assignment algorithms to determine a proper site for each cell in the decomposition and form various (1-) -approximate CIVDs for some small fixed >0. Particularly, we consider two representative CIVD problems, vector CIVD and density-based CIVD, and show that both of them admit fast assignment algorithms; consequently, their (1-) -approximate CIVDs can be built in O (n ^\{3, d+1\}n) and O (n ^2 n) time, respectively.