  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 $\mathbb{R}^d$, and determines the
influence-based Voronoi cell in $\mathbb{R}^d$ 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 $\mathbb{R}^d$ 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\log n)$ time, the
AI decomposition partitions the space $\mathbb{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-\epsilon)$-approximate CIVDs for some small fixed $\epsilon>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-\epsilon)$-approximate CIVDs can be built
in $O(n \log^{\max\{3,d+1\}}n)$ and $O(n \log^{2} n)$ time, respectively.
