1
$\begingroup$

I was trying out a question in Wellin's Programming with Mathematica that says the following.

Question: Given a set of points in the plane (or 3-space), find the maximum distance between any pair of these points. This is often called the diameter of the pointset.

What I did:

Clear[x,y,pointset];
pointset={{1,5},{2,6},{4,2}} (* Set of coordinates*)
distance[{x_List,y_List}]:=Sqrt[Total[(x-y)^2]]; (*Euclidean distance function*)
Max[Map[distance,Flatten[Outer[List,pointset,pointset,1],1]] 
(* Outer will give all possible pairings of the coordinates, 
   Flatten make the list into a collection of pairs of coordinates, 
   Map will apply the distance function to all the pairs,
   and Max do the obvious thing
*)

For the example given above, I ran it and obtain $2\sqrt{5}$ which I expect. My problem come afterwards, I want to create a function that takes in pointset as argument and gives out the diameter. As I know the procedure above works, I defined the function as follows.

diameter[x_List]:=Max[Map[distance,Flatten[Outer[List,x,x,1],1]]

and then I ran, diameter[pointset]. The output gave me this.

Max[distance[{{{1,5},{1,5}},{{1,5},{2,6}},{{1,5},{4,2}}}]]....

While I understand that the output happened because distance is tried to be applied to the wrong type of object, I am unclear on where I went wrong. Thus, my questions are:

  1. How do I fix the function such that distance is applied at the correct level?
  2. Why does this happen? I expected it to work as I literally just copy pasted the working code and change the parameter pointset to x.

Thank you in advance for the read and replies.

Edit1: Based on suggestion from @evanb, I modified the codes into the following.

diameter[x_List]:=Max[Map[distance,Subsets[x,{2}],1]]
diameter[pointset]

which still doesn't work. However, Max[Map[distance,Subsets[pointset,{2}],1]] gives the desired answer.

Edit2: @belisarius suggested another alternative approach and checked that the code works. Still trying to find a definitive explanation to why I couldn't get the answer on my version of Mathematica 10.

$\endgroup$
  • 1
    $\begingroup$ It seems like there's a tiny bug in the code you wrote: in both places, don't you mean Outer[ and not Outer,? When I make that fix, diameter[pointset] gives 2 Sqrt[5]. $\endgroup$ – evanb Sep 17 '14 at 0:55
  • $\begingroup$ Also, you're likely better off using Subsets[x,{2}] to accomplish what you're doing with Flatten and Outer. It should reduce redundant calculations. $\endgroup$ – evanb Sep 17 '14 at 1:00
  • $\begingroup$ @evanb Thank you; Firstly, for pointing out that typo. What I intended was for it to be Outer[, as you spotted. However, diameter[pointset] still gave me that long output. Secondly, for pointing out the Subsets[] Command, I didn't know it exist. $\endgroup$ – BeerR Sep 17 '14 at 1:13
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – Dr. belisarius Sep 17 '14 at 12:36
4
$\begingroup$
diameter[x_List] := Max[EuclideanDistance @@@ Subsets[x, {2}]]
diameter[pointset]
(* 2 Sqrt[5] *)

Now, let's improve the performance "a little bit". I believe the maximal distance will be realized at the points' convex hull (I'll not demonstrate it,but it's quite intuitive).

Now, if you have a lot of points Mathematica provides a convenient and fast way to find the Convex Hull. Let's use it and test the performance with and without it:

<< ComputationalGeometry`
pointset = RandomReal[{0, 1}, {3000, 2}];
diameter[x_List] := Max[EuclideanDistance @@@ Subsets[x, {2}]]

Timing[diameter[pointset]]
Timing[ch = ConvexHull@pointset; diameter[pointset[[ch]]]]

(* {45.328125, 1.39892}
   {0.061250,  1.39892}
*)

Now,YMMV but that's 45 vs .06 secs. Not bad at all for a little improvement ;)

$\endgroup$
  • $\begingroup$ Thank you for the suggestion of an alternative approach. However, I am still confused on why the function I defined does not work. $\endgroup$ – BeerR Sep 17 '14 at 1:57
  • $\begingroup$ @Beer Your fucction works. ClearAll["Global`*"]; pointset = {{1, 5}, {2, 6}, {4, 2}}; distance[{x_List, y_List}] := Sqrt[Total[(x - y)^2]]; diameter[x_List] := Max[distance /@ Flatten[Outer[List, x, x, 1], 1]]; diameter[pointset] $\endgroup$ – Dr. belisarius Sep 17 '14 at 2:06
  • $\begingroup$ Thanks for checking the code. I find it weird that both you and evanb actually confirmed that the code works (which I really think it should), but I couldn't get it to work on my own computer. I am guessing that it might have something to do with my version (Mathematica 10). May I know what version you are running? $\endgroup$ – BeerR Sep 17 '14 at 2:20
  • $\begingroup$ @BeerR Try this instead. It does the same thing as your function diameter[x_List] := Max[EuclideanDistance @@@ Flatten[Outer[List, x, x, 1], 1]] $\endgroup$ – Dr. belisarius Sep 17 '14 at 2:29
  • $\begingroup$ I am grateful and have tried the approach that you suggested. I have also found a workaround to find it using Table[]. I am just still confused on why it doesn't work only on my system. $\endgroup$ – BeerR Sep 17 '14 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.