       Re: The farthest apart points problem

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

```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