A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams (Q340524)

The authors observe that although there exist algorithms for nearest-site abstract Voronoi diagrams [\textit{R. Klein} et al., Comput. Geom. 42, No. 9, 885--902 (2009; Zbl 1173.65014)] and farthest-site abstract Voronoi diagrams [\textit{K. Mehlhorn} et al., Int. J. Comput. Geom. Appl. 11, No. 6, 583--616 (2001; Zbl 1074.68643)], but no efficient construction algorithms for order-\(k\) abstract Voronoi diagrams were available. Therefore, the authors develop here a randomized divide-and-conquer algorithm to compute the order-\(k\) abstract Voronoi diagram in expected \(O(kn^{1+\epsilon})\) basic operations, based on Clarkson's random sampling technique (see [\textit{K. L. Clarkson}, Discrete Comput. Geom. 2, 195--222 (1987; Zbl 0615.68037)]) and one additional axiom that the number of vertical tangencies of a bisector is \(O(1)\). This algorithm is applicable to a variety of concrete order-\(k\) Voronoi diagrams, such as point sites in any convex distance metric or the Karlsruhe metric, disjoint line segments and disjoint convex polygons of constant size in the \(L_p\) norms, or under the Hausdorff metric.