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