Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1996
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*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 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