MathGroup Archive 1996

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: The farthest apart points problem

  • To: mathgroup at
  • Subject: [mg5032] Re: The farthest apart points problem
  • From: dreece at (Daryl Reece)
  • Date: Sat, 19 Oct 1996 16:40:34 -0400
  • Organization: MindSpring Enterprises, Inc.
  • Sender: owner-wri-mathgroup at

peter at (unk) wrote:

>In article <4t6b17$7d3 at>, rigon at says...
>>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,
>A neat way of doing what you want is to use Outer.
>I works with ver 2.2.3
>do this:
>dist1[aa_,bb_]=Sqrt[(aa-bb).(aa-bb)]; (*arbitrary dimension distance func. *)

>b={{1,1,1},{3,3,3}} (*samle points*)

>and finally:
>you get:
>{Sqrt[3], 3 Sqrt[3], Sqrt[3], Sqrt[11], Sqrt[3], Sqrt[11], Sqrt[3], Sqrt[11]}

>i.e. the distance between of all combinations of the two sets of points a,b
>in your case a = b should be a list of the points in the polygon.
>To find the max of the distances just do Max[%//N]
>The two last aguments (level specifications) in Outer I have seen documented 
>only in
>Mathematica Journal vol 6 issue 3 you can also look in MJ vol 1 issue 1, I 
>think the last
>ref. uses a trick to avoid the level specefication that vas not available in 
>early MaMa versions
>/Peter W
>e-mail peter at

I might suggest an improvement upon this scheme.

dist[{a_,b_}]:= Sqrt[Plus @@ ((a-b)^2)]
dist /@ KSubsets[pts,2]

This eliminates the duplicate calls of calculating the distance from a
to b and from b to a.

The time traials I ran showed a 50% improvement for 100 points.


  • Prev by Date: Re: file name as mathematica function parameter
  • Next by Date: LISREL & PLS packages available
  • Previous by thread: Re: file name as mathematica function parameter
  • Next by thread: LISREL & PLS packages available