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$
4
  • 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, 2014 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, 2014 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, 2014 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$ Sep 17, 2014 at 12:36

1 Answer 1

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$
8
  • $\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, 2014 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$ Sep 17, 2014 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, 2014 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$ Sep 17, 2014 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, 2014 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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