Dynamic Upper Envelope of lines in the plane There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey
Davenport-Schinzel sequences and their geometric applications.

Are there any known algorithms / data structures for the dynamic version of the same problem? That is, we want to maintain the upper envelope of a set of lines in the plane under the following operations:


insert$(\ell$): adds line $\ell$ to the set
delete$(\ell)$: removes line $\ell$ from the set
query$(x)$: return the line with $x$ coordinate in the upper envelope. In other words, return the line in the set which is first hit by a vertical downward ray from the point $(x, \infty)$.
"someone" is right.  Timothy Chan's paper "Dynamic Planar Convex Hull Operations in
Near-Logarithmic Amortized Time" appears to solve the problem with insertions/deletions taking $O(\log ^{1+\epsilon}n)$ amortized time, and queries taking $O(\log n)$ time.  He solves your problem which is dual to the convex hull problem.