Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
Do you want a manual method or an algorithm? – NoChance 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: – NoChance 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

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.

Well, this reduces it to a finite problem, thought whether it is fast enough for your purposes, let alone optimal, I cannot say.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.