A Linear time algorithm for computing the Voronoi diagram of a convex polygon
Alok Aggarwal, Leonidas Guibas, James B. Saxe, Peter W. Shor · 1987
We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram of n points in the plane can be computed in Θ(n) time when these points form the vertices of a convex polygon in, say, counterclockwise order. This settles an outstanding open problem in computational geometry. Our techniques can also be used to obtain linear time algorithms for computing the farthest-point Voronoi diagram and the medial axis of a convex polygon and for deleting a vertex from a general planar Voronoi diagram.