-1
$\begingroup$

You are given n nonvertical lines in the plane, labeled $L_1, ..., L_n$, with the $i^{th}$ line specified by the equation $y = a_i x + b_i$.

We will make the assumption that no three of the lines all meet at a single point. We say line $L_i$ is uppermost at a given $x$-coordinate $x_0$ if its $y$-coordinate at $x_0$ is greater than the $y$-coordinates of all the other lines at $x_0$: $a_i x_0 + b_i > a_j x_0 b_j$ for all $j \neq i$.

We say line $L_i$ is visible if there is some $x$-coordinate at which it is uppermost-intuitively, some portion of it can be seen if you look down from "$y = \infty$".

Give an algorithm that takes $n$ lines as input and in $O(n\log n)$ time returns all of the ones that are visible.

Hint: Use divide-and-conquer approach.

Note: This question is taken from Here. Also, The answer is available as a code in java. But i can't understand what it does.

$\endgroup$
0
$\begingroup$

The solution you linked to makes use of two simple yet important observations: Let two lines $L_1, L_2$ of slope $m_1, m_2$ and intercept $b_1, b_2$.

  • If $m_1 = m_2$ then only the line of greater intercept is visible, otherwise they're both visible.
  • Their intersection is characterized by the relation $|(b_1 - b_2)| / |(m_1 - m_2)|$.

Given a set of $0, 1$ or $2$ lines, the solution is then computed in $O(1)$ time ; those will be our base cases.

Given a set S of $n$ lines, the solution is computed using the following algorithm :

HLR(S)
  Let S1, S2 sets of line
  S1 = HLR(FirstHalf(S))
  S2 = HLR(SecondHalf(S))
  Return Merge(S1, S2)
End

With FirstHalf(S) and SecondHalf(S) being exclusive subsets of S of cardinality $n/2$ (or sometimes $1$).

To merge the intermediate results, you need to set an order relation on the lines (based on their slope and intersect of course) and compare lines 2 by 2. If one hides another, then you can assume that the later will never be visible and thus can safely be removed from the set of solutions. The method is properly explained in the comments of the program you linked, and makes use of the intersection relation I mentioned. As described there, there are about $2n$ treatments.

We're dividing the problem in $2$ subproblems of size $n/2$ each. The master theorem gives the following relation: $T(n) = 2 * T(n/2) + f(n)$. Here, $f(n) = 2n = \Theta(n^1 \log^0 n)$. As $\log_2 2 = 1$, it follows that $T(n) = \Theta(n^{\log_2 2} \log^{0+1} n) = \Theta(n \log n)$, which implies that it is also in $O(n \log n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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