A Sweepline Algorithm for Higher Order Voronoi Diagrams
Maksym Zavershynskyi, Evanthia Papadopoulou · 2013
We present an algorithm to construct order-k Voronoi diagrams with a sweepline technique. The sites can be points or line segments. The algorithm has O(nk2log n) time complexity and O(nk) space complexity.