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: [mg4509] Re: The farthest apart points problem
  • From: danl (Daniel Lichtblau)
  • Date: Fri, 2 Aug 1996 02:22:37 -0400
  • Organization: Wolfram Research, Inc.
  • Sender: owner-wri-mathgroup at wolfram.com

In article <4t6b17$7d3 at dragonfly.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 pairs is separated by the largest
> distance ?
> 
> Thank you in advance for any help,
> 
> Riccardo
> 
> 


I'll show an algorithm with O(n*log(n)) complexity, n being the number of  
points. I do not know whether this is optimal (and simplicity is in the  
eye of the beholder). The basic idea is to form explicitly the n-gon for  
this convex hull, and then use knowledge of who is neighbor to whom to  
find candidate maximally separated pairs. If you have the hull explicitly,  
that is, know the neighbors of each point, then it becomes O(n).

(i) Pick a vertex v_0. Take distances from v_0 to all other points. Call a  
vertex that minimizes these distances (there are at most two such) v_0min.  
Call a maximizing vertex v_0max.

(ii) One neighbor of v_0 is v0_min in the convex hull. Call lv0 the line  
between these neighbors. Form lines between v0 and all remaining n-2  
vertices. Order these according to angle, measured counter-clockwise (CCW)  
from the ray emanating at v0, going through v_0min. This ordering gives  
the convex hull as an n-gon. Note that angle on this n-gon must strictly  
increase once we are off lv0. To handle colinearity it suffices to order  
those points with angle zero or pi by distance from v_0.

(iii) Each vertex has one or two corresponding vertices at maximal  
distance from it (call these maximizing co-points). As one such pairing  
suffices, we have Ceiling(n/2) candidate pairs. Clearly v_0 and v_0max  
form one such pair. By convexity all other pairs have one point on each  
side of lv0 or else have v_0max as one vertex (exception that can be  
ignored: the other point, if such exists, that maximized distance from  
v_0). Moreover as we move over one point CCW from v_0 toward v_0max, the  
maximizer co-point moves CCW. We have found it once distances no longer  
increase.

Let v_1 be the neighbor CCW from v_0. Take distance from v_1 to v_0max, to  
point immediately CCW from v_0max, to next point CCW, until distance no  
longer increases. This gives v_1max, the maximizing co-point for v_1. Let  
v_2 be the neighbor CCW from v_1. Take distance to v_1max, to point CCW  
from v_1max, etc. until distances no longer increase, and obtain v_2max.  
Continue in this fashion until we have maximizing co-points for all points  
up to v_0max.

(iv) We have our candidate pairs. Find the biggest.

Complexity: Steps (i), (iii), and (iv) are O(n). Step (ii) requires  
sorting n-2 values, hence can be done in O(n*log(n)). If there are many  
points and the angles formed with lv0 are reasonably well distributed  
between 0 and 180 in degrees, then a practical improvement might be to  
first sort the angles into buckets where most significant digit is zero,  
is one, ..., is 179, and then sort each bucket. The expected complexity is  
then O(n*log(n/180)).

Note that step (iii) can be improved, and step (iv) removed, as follows.  
Continue (iii) so long as maximal pair distances increase. When they cease  
to do so, stop and your maximal distance is that of the last maximal pair  
found for which distances were increasing. If maximal pair distances are  
initially decreasing (that is, |v_0-v_0max| > |v_1 - v_1max|) then 
reverse direction and go clockwise instead.


Daniel Lichtblau
Wolfram Research, Inc.
danl at wolfram.com

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


  • Prev by Date: Re: The farthest apart points problem
  • Next by Date: SphericalPlot3D, spherical harmonics, and coloring them?
  • Previous by thread: Re: The farthest apart points problem
  • Next by thread: Re: The farthest apart points problem