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