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: [mg4620] Re: The farthest apart points problem
  • From: Riccardo Rigon <rigon at csrp.tamu.edu>
  • Date: Wed, 21 Aug 1996 03:25:36 -0400
  • Organization: EOWR TAMU
  • Sender: owner-wri-mathgroup at wolfram.com

Based on the suggestions  I had from the news
group, I did this mathematica program  calculating 
the two farthest apart points in a set of vertex 
of a convex hull.

Unfortunately I could not find in my libraries
the Shamos and Preparata textbook suggested by 
David Eppstein who I thanks anyway. 
Other contributions come from D aniel Lichtbau,
Bruce Alan and a forth guy whose name unfortunaly 
I have lost.

This is my solution


SetToPointDistance[pt_,set_]:=(Plus  @@ 
((#-pt)^2))& /@set

diameter[hd_]:={hd[[1,1]],hd[[3,1]],Sqrt[N[hd[[1,2
]]]]}/;
     (Length[hd[[2]]]==0 )

diameter[hd_]:={hd[[1,1]],Last[hd[[2]]],Sqrt[N[hd[
[1,2]]]]}/;( 
      Length[hd[[3]]]==0)
	
diameter[hd_]:=Module[{dd,nx},
dd=SetToPointDistance[hd[[2,1]],hd[[3]]];
nx=Max[dd];
		If[nx		< hd[[1,2]],
			diameter[{hd[[1]],Drop[hd[[2]],1],hd[[3]]}],
       diameter[{{hd[[2,1]],nx},Drop[hd[[2]],1],
          Drop[hd[[3]],Position[dd,nx][[1,1]]-1]}]
			]
]

Diameter[data_]:=Module[{pt=First[data], 
st=Rest[data]},
dis=SetToPointDistance[pt,st];
mx=Max[dis];
diameter[{{First[data],N[mx]},Take[st,#],Drop[st,#
-1]}]&  @
       ( Position[dis,mx][[1,1]])
		]

ON2[data_]:=Max[Sqrt[N[SetToPointDistance[#,data]& 
/@data]]]


ON2 is the trivial O(N^2) solution

Diameter[data] where "data" contains the vertex of 
the convex hull works a little bit faster 
(ordered).

The  function "diameter" is based on the fact that 
given a vertex and the most distant other vertex 
from it, the farthest apart points is either:

1) the pair one already has (say A and  B);

2) a pair which one point stay from one side of 
the line  AB and the other on the other side.

3) a pair of ehich one point is point B and the 
second is on one of the two sides


Any better/more elegant/faster solution ?

Riccardo Rigon

==== [MESSAGE SEPARATOR] ====


  • Prev by Date: Re: Matching random numbers
  • Next by Date: Postfix (//) with Options? (SUMMARY)
  • Previous by thread: Re: The farthest apart points problem
  • Next by thread: Re: The farthest apart points problem