A linear-time algorithm for computing the Voronoi diagram of a convex polygon (Q911267)

The main result of the paper is a linear-time algorithm for the problem of constructing the convex hull of a set of n points in three dimensions whose projections on the xy plane form the (counterclockwise ordered) set of vertices of a convex polygon. As consequences, linear time algorithms are obtained for computing the Voronoi diagram and the furthest-point Voronoi diagram for a convex polyon vertex set, for updating the Voronoi diagram after deletion of a point site, for constructing the medial axis of a convex polygon, for finding the largest inscribed circle and the largest empty circle centered inside a convex polygon. These results are also used to obtain better time bounds for some algorithms for proximity-related problems. Some open problems are posed.