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 pk, k = 1,...,n the distance function defined by the euclidean distance between pk 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.
ASJC Scopus subject areas
- Modeling and Simulation
- Computational Theory and Mathematics
- Computational Mathematics