i just find out that after finding the convex hull we can do the rest in
O(h)
(See Jalaj Jaiswal's post: Computational Geometry)
On Tue, Jun 29, 2010 at 1:31 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> @Amit: in most of the algos for convex hull the result would be the
@Amit: in most of the algos for convex hull the result would be the points
on the hull in clockwise or counter clockwise order
now we have a point P that we want to find the farthest point from it now
imagine the list as if it's circular and the range where binary search is
applied on starts after
If the points are already sorted by one of the coordinates or by the angle
to a fixed vector, then the algorithm takes O(*n*) time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.c
@Amir
I think convex hull will take O(nlogn) time
Can u tell a O(n) algo
On Sun, Jun 27, 2010 at 9:43 PM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> it's obvious that these 2 points must be on the convex hull
>> so first find the convex hull O(n)
>>
>
>
>
--
Regards
Jit
@ above can u specify how to apply binary search here as the points are not
in increasing manner...or am i missin something
On Sun, Jun 27, 2010 at 9:43 PM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> it's obvious that these 2 points must be on the convex hull
> so fir
it's obvious that these 2 points must be on the convex hull
so first find the convex hull O(n)
then for each point on the hull find the farthest point by binary
search (since if you turn on the hull the distance to the base point
increases until the farthest point then it starts to decrease)
if the
Hi , can anyone tell me how to find the diameter of a set of N points
i.e the distance between the 2 most farthest points efficiently
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegro
