The symmetric all-furthest- neighbor problem

Given a set P of n points on the plane, a symmetric furthest-neighbor (SFN) pair of points p, q is one such that both p and q are furthest from each other among the points in P. A pair of points is antipodal if it admits parallel lines of support. In this paper it is shown that a SFN pair of P is both a set of extreme points of P and an antipodal pair of P. It is also shown that an asymmetric furthest-neighbor (ASFN) pair is not necessarily antipodal. Furthermore, if P is such that no two distances are equal, it is shown that as many as, and no more than, ⌊n/2⌋ pairs of points are SFN pairs. A polygon is unimodal if for each vertex p_k, k = 1,...,n the distance function defined by the euclidean distance between p_k and the remaining vertices (traversed in order) contains only one local maximum. The fastest existing algorithms for computing all the ASFN or SFN pairs of either a set of points, a simple polygon, or a convex polygon, require 0(n log n) running time. It is shown that the above results lead to an 0(n) algorithm for computing all the SFN pairs of vertices of a unimodal polygon.