### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 747-754 |

Number of pages | 8 |

Journal | Computers and Mathematics with Applications |

Volume | 9 |

Issue number | 6 |

DOIs | |

State | Published - 1983 |

### ASJC Scopus subject areas

- Modeling and Simulation
- Computational Theory and Mathematics
- Computational Mathematics