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] ====