# Line segment k-intersection

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!

-
 Do you want a manual method or an algorithm? – Emmad Kareem Oct 10 '11 at 19:29 @Emmad: "random-access list" was sorta kinda a tipoff that OP intends to do this on a computer... – J. M. Oct 10 '11 at 22:12 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. – deinst Oct 10 '11 at 22:40 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: en.wikipedia.org/wiki/Line_segment_intersection – Emmad Kareem Oct 10 '11 at 22:53 @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. – Gerry Myerson Oct 11 '11 at 1:08
show 1 more comment

I interpret the question this way (and if I've misinterpreted, kindly ignore this answer): you have $n$ inequalities of the form $$a_i\le x\le b_i$$ and you want to know whether there is an $x$ that satisfies at least $k$ of them. If there is such an $x$, then there is an $a_i$ that satisfies $k$ of them (there's also a $b_i$ that satisfies at least $k$ of them), so all you have to do is check each of the $a_i$ to see if it works.