n points and a line

of the y-axis). We want to find the segment of the lower convex
hull that intersects the y-axis. The following process is used.
We have a current segment through two points p and q (one in the
negative and one in the positive half-space). If no point lies
below the line through the current segment we are done. Otherwise,
we are given a random point below the line and the segment is
updated. Emo Welzl has shown that the process terminates in an
expected number of log^2 n steps.

I heard him give a talk about the problem, liked it, and will try
to replay the talk for you.