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] ====