An O(nlogn) algorithm for the all-farthest-segments problem for a planar set of points

In this paper, we propose an algorithm for computing the farthest-segment Voronoi diagram for the edges of a convex polygon and apply this to obtain an O(nlogn) algorithm for the following proximity problem: Given a set P of n (>2) points in the plane, we have O(n2) implicitly defined segments on pairs of points. For each point p∈P, find a segment from this set of implicitly defined segments that is farthest from p. We improve the previously known time bound of O(nh+nlogn) for this problem, where h is the number of vertices on the convex hull of P.