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
    @GerryMyerson, wow, I did not think of this!2011-10-11

1 Answers 1

1

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.