9
$\begingroup$

I have multiple parabolas ($y = ax^2 + bx + c$) which may intersect with each other (or some of them may not intersect). I am trying to find upper segments of these parabolas, e.g. bold part in the picture:

intersecting parabolas

I need to find it in $O(n\log n)$. There's a solution for line version of this problem: https://stackoverflow.com/questions/7420193/how-to-find-upper-envelopes-of-intersected-lines-in-onlogn

But I cannot find a way to apply this solution to quadratic version since there are $a$, $b$ and $c$ variables to consider. Any help will be appreciated.

  • 0
    A preliminary transformation you can do to your parabolas is to "complete the square" so they all look like $a(x+d)^2+f$, and then you can sort them from left to right...2011-09-15
  • 0
    @J.M.: That's only part of it. Parabola $B$ in the diagram might be wider than parabola $A$, so that it breaks out to the left of $A$ although its $d$ parameter is smaller. (Yes, smaller -- perhaps $a(x-d)^2+f$ would be a better parameterisation.)2011-09-15
  • 0
    @Tony: Yeah, I thought of the "wide parabola" case after commenting; at the very least, the "completed square" form, I think, is more convenient for further manipulations anyway. (Your parametrization is indeed better.)2011-09-15
  • 0
    After the sort by increasing $d_n$, the n-th parabola $p_n = a_n(x-d_n)^2 + f_n$ can cross all parabolas $1, ..,n-1$, giving an $O(n^2)$ algorithm.2011-09-15
  • 0
    Is coefficient $a$ negative for every parabola?2011-09-15
  • 0
    In any case, the leftmost and rightmost upper segments will belong to the parabola with the largest value of $a$, not $d$...2011-09-15

2 Answers 2