Voronoi diagrams and arrangements (Q1079823)

The authors propose a natural general framework for defining and dealing with diagrams of Voronoi type. An important concept is the notion of an \(f_ E\)-arrangement over a domain D, i.e. the partition of \(D\times {\mathbb{R}}\) induced by a collection \(f_ E\) (indexed by the finite set E) of real valued functions on D. E.g. let f be a real valued function on D, then \(f^+=\{(x,r)\in D\times {\mathbb{R}}| 0<f(x)-r\}\) is a lower hemispace of f, and the upper hemispace \(f^-\) and the surface \(f^ 0\) are analogously defined. In such a way cells of an \(f_ E\)-arrangement can be defined, lemmas about order-equivalent collections \(f_ E\) and \(g_ E\) are proven. If \(f_ E\) is a collection of affine or quadratic functions then algorithmic optimization problems are surveyed. Voronoi diagrams are introduced in this manner. Let \(R_ f\) be a function from D to the index set E defined by \(R_ f(x)=\{e\in E| f_ e(x)=\min_{i\in E}f_ i(x)\}.\) \(R_ f\) induces an equivalence relation \(\rho_ f\) on D, where for x,y\(\in D\), x \(\rho\) \({}_ f y\Leftrightarrow R_ f(x)=R_ f(y)\). The partition of D, induced by \(\rho_ f\), is called the Voronoi diagram on D with respect to \(f_ E\), for short \(VOD(f_ E)\). The equivalence classes of the partition are called Voronoi cells. The classical concept of Voronoi region can also be introduced in this way. A typical algorithmic result is Theorem 3.2. Let \(D={\mathbb{R}}^ d\) for some \(d\geq 1\). Let \(f_ E\) be a collection of n affine or quadratic functions on \({\mathbb{R}}^ d\). Then \(VOD(f_ E)\) can be constructed in worst case time O(n log n) for \(d=1,2\) and \(O(n^{[(d+1)/2]})\) for \(d\geq 3\). This is optimal for odd d and for \(d=2.\) Results about order-k and degree-k Voronoi diagrams and about intersection problems complete this informative survey.