MathGroup Archive 1996

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

Search the Archive

Re: The farthest apart points problem


Riccardo Rigon <rigon at csrp.tamu.edu> 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 comp.graphics.algorithms 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.

==== [MESSAGE SEPARATOR] ====


  • 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