1
$\begingroup$

Could you please help me to design the following algorithm:

I have a random-access list of line segments defined by a pair of points $[x^s_i; x^e_i]$. The list is initially unsorted, but of course can be sorted by left or right coordinate in $n \log n$.

I need to determine whether at least $k$ of these segments intersect or not as quick as possible (asymptotically).

Thank you very much in advance!

  • 0
    Do you want a manual method or an algorithm?2011-10-10
  • 0
    @Emmad: "random-access list" was sorta kinda a tipoff that OP intends to do this on a computer...2011-10-10
  • 0
    What do you mean when you say $k$ of them intersect? You could mean that there is a point contained in $k$ segments. You could mean that there are $k$ lines each of which intersects the $k-1$ others. You could mean that there are $k$ lines that form a connected component. You could mean that there are at least $k$ intersections. You could mean something else entirely It is likely that some variant of Bentley Ottman search will serve your purpose.2011-10-10
  • 0
    At first I though this would be easy, but when I looked at the link below, I found that it is not trivial (if you have many segments) - The link is: http://en.wikipedia.org/wiki/Line_segment_intersection2011-10-10
  • 0
    @Emmad, that link concerns line segments in the plane. I may be misreading here, but I think OP is asking about line segments on a line, which might be a much easier problem.2011-10-11
  • 0
    @GerryMyerson, wow, I did not think of this!2011-10-11

1 Answers 1