Influence-based Voronoi diagrams of clusters

Ziyun Huang, Danny Z. Chen, Jinhui Xu

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 Rd, a collection C={C1,C2,…,Cn} where each Ci⊆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 Rd, 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(T2(N)Nlog2⁡N+T1(N)) time, where N is the total cardinalities of clusters in C, ϵ>0 is a small constant, and T1 and T2 are functions measuring how efficiently F(C,q) can be evaluated.

Original languageEnglish (US)
Article number101746
JournalComputational Geometry: Theory and Applications
StatePublished - Jun 2021

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Influence-based Voronoi diagrams of clusters'. Together they form a unique fingerprint.

Cite this