0
$\begingroup$

Suppose we have $n$ lines $L_1, L_2, \dots, L_n$, where $L_i$ has the equation $y = a_i x + b_i$. We call $L_i$ the highest line at $x_0$ if for each $j \in \{1, 2, \dots, n\}$

$$a_i x_0 + b_i \ge a_j x_0 + b_j.$$

  • Goal: Find an algorithm in $O(n \log n)$ time to return a set of lines that are the highest lines in at least one point.

  • Hint: Use the divide and conquer technique.

Since we should use divide and conquer technique, I think I should split the problem into two subproblems with size of $n/2$ and try to solve these two first. I don't know what to do next. Thanks in advance.

$\endgroup$
5
  • 2
    $\begingroup$ So try splitting hte problem as you describe and see where you get! $\endgroup$ Commented Apr 27, 2017 at 18:28
  • $\begingroup$ @DavidRicherby I think I would end up with some pairs of lines. What about this approach? In each of these pairs I would save the one which has the greater slope, and let go of the other one. question: Is there more than two answers to this question? I mean could there be another answer rather than the lines which have the most slope values? (either positive or negative) $\endgroup$ Commented Apr 27, 2017 at 19:03
  • $\begingroup$ You can sort in nlogn by slopes. In the case of equality by $b$. If the lines are the same, then both might be the result, so yes, there are more solutions. If you consider the naive solution, just evaluating each line at each point it gets the $n^2$ running time, so the objective is to make it faster. I do not know whether the hint is really needed or if divide and conquer sorting would count. And yes, the answer simply by taking slopes is wrong, take $x + n$ and $2x$, the second one has the greater slope, but the first one has maximal value at given points. $\endgroup$
    – Evil
    Commented Apr 28, 2017 at 1:37
  • $\begingroup$ @Evil I understood why those are not just 2 answers. Thank you very much. I'm still seeking for a O(nlogn) approach. $\endgroup$ Commented Apr 28, 2017 at 9:12
  • $\begingroup$ @RodrigodeAzevedo Thank you for your excellent edit. Sorry for my poor English :/ $\endgroup$ Commented Apr 28, 2017 at 17:15

2 Answers 2

0
$\begingroup$

If the lines are unlimited (as they seem to be) then the way to go seems to divide the lines by their slope.

Preprocessing:

Sort all the lines lexicographically by their slope and constant term. This allows to remove each line which is parallel to some higher-placed line. The ordering is also used to split the lines into subroups depending on their slope later on.

Recursion:

Divide the lines into lines with positive and negative slope. For each group call recursion. From each recursion we get two lists, a list of top-lines (ordered as they appear on top from left to right) and a list of top-intersections of the top-lines (ordered by x-coordinate) corresponding to the points where one line takes over the previous one.

Now we only need to combine the two results we got from recursion. The algorithm passes through the intersection-point lists in parallel, going through positive-slope lines from right to left, and through negative-lines from left to right until the x-coordinates of the intersections meet. To do this properly, we need always make the step on the side with higher y-coordinate.

(I strongly suggest to draw it, it's easier to see in a picture. Imagine bunch of lines forming a "U"-shape and the algorithm descends with equal vertical speed on both sides until it reaches the lowest point of the "U"-shape.)

In this way we found a "middle" point where one positive- and one negative-slope top-line meet in a new top-intersection. From the list of lines we know which lines meet there and we can compute the intersection point they share (the lowest point of the "U"-shape).

We can now construct the total list of intersections of top-lines (all the point we went through + the new intersection point we found in the middle) and the list of the corresponding top lines.

Note that it might happen that all the positive-slope intersection might be too much to the left (so we do not get a "U"-shape). In that case we only get one positive- and one negative-slope line as a result, intersecting in an "V"-shape.

Now, how to split the groups in the recursion? Well, simply realize that by tilting (by less than 90 degrees) what the algorithm understands us "horizontal" none of the necessary properties is violated (within the subgroup). Thus the algorithm can again split the groups into smaller groups, while the left-right orderings remain consistent. So in fact we don't want to split lines into positive and negative slope, but simply split by the median slope each time. (splitting by the horizontal direction just makes it easier to understand)

Complexity:

Each level of recursion is linear-time in respect to the number of lines (going through lists in parallel, concatenation of lists, etc.). Since the lines are already ordered by their slope (from preprocessing), we can always split by the mean slope in linear time. So the total time is O(nlogn).

Hope the description is somewhat clear. I did not go into details as that would be lengthy.

$\endgroup$
2
  • $\begingroup$ Well, I couldn't get your answer. You are saying you want to sort by $a_i$ and $b_i$ s at first. Then you say you sort by keeping ordering by x and y coordinates... I'm confused. Can you be more specific? $\endgroup$ Commented Apr 28, 2017 at 11:23
  • $\begingroup$ I tried to improve my answer, maybe it helps. $\endgroup$ Commented Apr 28, 2017 at 19:22
-1
$\begingroup$

SORRY: I MIS-READ THE PROBLEM AS FIXING THE X COORDINATE FIRST:

Evaluate each line $L_i$ at $x_0$, yielding $y_i$. Collect all ordered pairs ($L_i$,$y_i$) and sort on the $y$ values. Top pair yields the desired line. [note: there may be more than one 'top line', in which case they will all be at the 'top' with the same $y$ value]

$\endgroup$

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