Finding upper segments of intersecting parabolas 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:

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.
 A: You are seeking what is called in the literature the upper envelope of a collection of $x$-monotone curves.  Actually, searching for "lower envelope" will give you more hits; obviously they are equivalent.  You might look at the CGAL implementation, e.g., via this link:

Update. To address joriki's comment, let me quote Theorem 6.5 (p. 137) from the Sharir-Agarwal book, Davenport-Schinzel Sequences and Their Geometric Applications:

Given a collection $\Gamma$ of $n$ $x$-monotone Jordan arcs, each pair of which intersect in at most $s$ points, the lower envelope of $\Gamma$ can be computed in $O(\lambda_{s+1}(n) \log n)$ time.

Because $s=2$ in the case of parabolas, the relevant term is $\lambda_3(n)$.
This $\lambda$-function is a combinatorial quantity that has been proved to
have certain bounds.  A tight bound is known for $\lambda_3(n)$: it is $\Theta( n \alpha(n) )$, where $\alpha(n)$ is the inverse of Ackermann's function, i.e. $\le 5$ in this universe. So the complexity in the theorem is just a hair above $O( n \log n)$.
A: [Note: The first version of this answer was incorrect; the comments refer to the incorrect version.]
I'll assume that the parabolas all open downward as in the diagram; if they don't, things might be more complicated. I'll take $y$ to increase downward to simplify things.
A parabola is the locus of points at equal distance from a point (the focus) and a line (the directrix). In the present case, all directrices are horizontal. If we weight the distance from the focus by adding the $y$ coordinate of the directrix, we can regard the parabola as the locus of points where this weighted distance from the focus is equal to the $y$ coordinate of the point. Above the parabola, the weighted distance from the focus is greater, and below the parabola, the $y$ coordinate is greater. For a point on the upper envelope, the weighted distance from the focus of the parabola forming the envelope is equal to the $y$ coordinate of the point, and the weighted distances from all other foci are less than or equal to this $y$ coordinate. Thus, if we form the additively weighted Voronoi diagram of the foci, the parabolic segments forming the upper envelope lie in the Voronoi regions of the corresponding foci.
It follows that the intersections at which the upper envelope switches from one parabola to another lie on edges of the weighted Voronoi diagram. The weighted Voronoi diagram can be computed in $O(n\log n)$ time, for instance using Fortune's algorithm; the modification for the additively weighted case is straightforward and is described in the original paper (Section 4). Since the weighted Voronoi diagram is a planar graph with minimal vertex degree $3$ and $n$ faces, Euler's formula implies that it has $O(n)$ edges. Thus, the upper envelope can be constructed in $O(n\log n)$ time by computing the weighted Voronoi diagram, finding the intersections of parabolas whose Voronoi regions share an edge, ordering the intersections according to their $x$ coordinates and traversing them from left to right to determine at which of them the envelope switches to a different parabola.
Also see these notes for a discussion of the relationship between the upper/lower envelope of a set of parabolas and a Voronoi diagram.
