Re: The farthest apart points problem
- To: mathgroup at smc.vnet.net
- Subject: [mg5032] Re: The farthest apart points problem
- From: dreece at atl.mindspring.com (Daryl Reece)
- Date: Sat, 19 Oct 1996 16:40:34 -0400
- Organization: MindSpring Enterprises, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
peter at su.se (unk) wrote:
>In article <4t6b17$7d3 at dragonfly.wolfram.com>, rigon at csrp.tamu.edu 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,
>>
>>Riccardo
>>
>>
>>
>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. *)
>a={{0,0,0},{0,2,2},{2,0,2},{2,2,0}}
>b={{1,1,1},{3,3,3}} (*samle points*)
>and finally:
>Flatten[Outer[dist1,a,b,1,1]]
>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 physto.se.
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.
-Daryl