The one-dimensional weighted Voronoi diagram (Q1071508)

Let \(S=\{p_ 1,...,p_ n\}\) denote a finite set of points on the x- axis, and let each \(p_ i\in S\) have an associated weight \(w(p_ i)>0\). The weighted Voronoi diagram WVD(S) of S is a partition of the x-axis into regions \[ reg(p_ i)=\{x| \quad | x-p_ i| /w(p_ i)\leq | x-p_ j| /w(p_ j),\quad p_ j\in S\}, \] for \(i=1,...,n\). Although \(reg(p_ i)\) may consist of O(n) disjoint intervals, the total number of intervals realized by WVD(S) can be shown to be bounded by 2n-1. Furthermore, WVD(S) can be constructed by a simple divide-and-conquer algorithm in optimal time O(n log n) and space O(n). Both results heavily rely on a two-dimensional interpretation of WVD(S) where, intuitively speaking, the weighted distance \(| x-p_ i| /w(p_ i)\) from \(p_ i\) is considered as some kind of speed an interval around \(p_ i\) expands with. The geometrical concept of WVD(S) and its analogues in dimensions two and three have applications in geography, economy, and biology.