Problem

[Mohammad Hossein Rohban]

Hi,
Consider this problem. A number of chords are given on a circle (each with
length less than 3.14159*r).
Give an O(n log n) algorithm to find minimum number of line segments (with
the center of the circle as one of their end points
and some other points on the circle as the other end points), that are
necessary to cover all chords (by covering, I mean each chord has at least
one intersection with a line segment.)
I tried to solve this problem, and I have devised an algorithm which runs
in O(n log n) time in cases that there exists a chord that contains no
right point of any other chords (considering counterclockwise direction.)
But of course this may not be happened in worst case and this cause the
algorithm to run in O(n^2) time.
Can anyone give an algorithm to solve this problem in O(n log n) time in
its worst case?

best regards,
Mohammad Hossein Rohban

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.