Services & Resources / Wolfram Forums
MathGroup Archive
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1996

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: The farthest apart points problem

  • To: mathgroup at
  • Subject: [mg4506] Re: The farthest apart points problem
  • From: j-waldby at (James Irl Waldby)
  • Date: Fri, 2 Aug 1996 02:22:34 -0400
  • Organization: University of Illinois at Urbana
  • Sender: owner-wri-mathgroup at

Riccardo Rigon <rigon at> writes:

> Let us have n points in a plane being the vertices of a convex hull. 
> Do you know a fast and simple algorithm to determine which pair
> is separated by the largest distance ?

Perhaps newsgroup would be a more
appropriate venue for the question.

If the n points are listed in adjacency order, p0, p1 ...
solve this in O(n) time: Find point p0' most distant from
first point p0.  The line p1,p1' crosses* p0,p0' and in
general the line pj,pj' crosses* pi,pi' if j=i+1, so as
you step through p1, p2, p3 ... finding p1', p2', p3' ... you never
need to back up in the list of points you look at to find pj'.

*That is, it either shares an endpoint (pj'==pi') or crosses.


  • Prev by Date: Re: bar charts with error bars?
  • Next by Date: Re: Two Dimensional Numerical Integration Packages
  • Previous by thread: Re: The farthest apart points problem
  • Next by thread: Re: The farthest apart points problem