# 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.

• If you simply sort by $y$ the query can't be just $log n$. You can find the bounds, but you'd still have to scan to the find the one that matches the criteria on $x$ -- that it intersects. – edA-qa mort-ora-y May 27 '12 at 10:25

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.

The problem can be solved using 2 Dimensional Range Trees with a slight augmentation.

2D Range Tree supports pre-processing of the $n$ points in $O(n*\log{n})$ time.
The query for enumerating all points in a rectangle defined by 4 points can be done in $O(k+\log{n})$ time. Where $k$ is the number of points in the rectangle.

Let us say you have the horizontal segment $s$ between points $(a,c)$ and $(b, c)$.
We invoke the query operation on rectangle defined by $(a,c)$ ,$(b, c)$, $(a, y_{max})$, $(b, y_{max})$. Where $y_{max}$ is the maximum among y-coordinates of given $n$ points.

In the $1^{st}$ level tree which is structured based on x-coordinates we might end up visiting the $2^{nd}$ level tree of at most $O(\log{n})$ nodes. And And each time we visit the $2^{nd}$ level tree of some node we should just return point with the smallest y co-ordinate in the y-range of rectangle. We finally return the point with minimum y-coordinate among at most $O(\log{n})$ such points. Each such traversal on $2^{nd}$ level tree takes $O(\log{n})$ time. So, the query time of this scheme is $O(\log^2{n})$