## Abstract

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_{1},C_{2},…,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(NlogN) in O(T_{2}(N)Nlog^{2}N+T_{1}(N)) time, where N is the total cardinalities of clusters in C, ϵ>0 is a small constant, and T_{1} and T_{2} are functions measuring how efficiently F(C,q) can be evaluated.

Original language | English (US) |
---|---|

Article number | 101746 |

Journal | Computational Geometry: Theory and Applications |

Volume | 96 |

DOIs | |

State | Published - Jun 2021 |

## All Science Journal Classification (ASJC) codes

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics