A new duality result concerning Voronoi diagrams (Q5899690)

A new duality between order-k Voronoi diagrams (k-V(P)) and convex hull is established. Using this background, a new algorithm for constructing k-V(P) for a set P of n points in \(E^ d\) is proposed. Let size(d,k) denote the maximal number of faces of k-V(P) in \(E^ d\). The given space-optimal algorithm requires 0(size(d,k)) space. In \(E^ 2\) it gives also the most time-efficient solution for \(k<\sqrt{n/\log n}\). The given algorithm is an interesting generalization to order k of the known algorithm given by K. Brown which computes 1-V(P) in \(E^ d\) via convex hull in \(E^{d+1}\).