Finding the point nearest to the x-axis over some segment

I have problem with solving the following exercise


Given the set $P$ on $n$ points in two dimensions, build in time $O(n\log n)$ a data structure of $P$ such that given a horizontal segment $s$ find the first point that $s$ touches when moving upwards from the x-axis in time $O(\log^2n)$.

The preprocessing time is equivalent to sorting, so we can perform sorting by one dimension.

The query time is a little bit confusing - $\log^2$n. I would say it's $\log n$ binary searchs but it doesn't make sense.

The $\log^2(n)$ implies that at each node in the search you probably have to do another search. This gave me an idea. Let's construct a tree from the input data:
$$\text{LeafNode} = \{ x, y \}$$
$$\text{NonLeafNode} = \{ \text{Min}_x, \text{Max}_x, \text{MinYPoint} \}$$

Each node will partition the input space into two non-overlapping ranges. The root node will thus be the complete range of $x$ in the input data with the minimum $y$ value.

Then we define a recursive search function that takes a node and the horizontal line segment and returns either the minimum $y$ or $\text{NotFound}$ condition (for simplicity say the value of $\infty$ represents $\text{NotFound}$).

GlobalMinY = Infinity

search( Node, segment ) -> MinY
    if Node does not overlap segment
        return Inf
    if Node.MinY >= GlobalMinY
        return Inf
    if Node is sub-segment
            GlobalMinY = Node.MinY
        return Node.MinYPoint

    return Min( search(Node.Left), search(Node.Right) )

It's easy enough to construct these tree using a modified merge-sort, so construction time is within the bounds. What I'm having a hard time showing is that the search time is within the required bounds.

Search time: Other than the root node, at each node one of the Left or Right nodes will either be included completely or excluded completely. Only one of them can have a partial overlap. If this is correct the time is $2 \log(n)$ -- from root we do two searchs and each follows only a single path through the tree. I'm not even sure the GlobalMinY optimization is needed.

StackExchange Computer Science Q#2101, answer score: 5