On Nov 20, 1:46 pm, Monty <[EMAIL PROTECTED]> wrote:
> Hi Frndz,
>
> If there are n points on the circumference of circle(order not
> known) ,how can we find out the closest pair in complexity O(nlgn)...
>
> pls help with the answer... thnx.
The closest pair will be the closest pair measured by distance along
the circle.
Select a start point on the circle and measure distance to each
point in one direction around the circle.
Now sort.
Then add 2pi to each value to create another set of n values (2n in
total all sorted).
Then find closest pair in O(n) time by comparing consecutive
values.
If closest pair has first value from first set of points and
second value from second pair of points then shorter arc
along circle joining points contains start point.
Ralph Boland
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
