Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1996
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

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: [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





  • 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