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.

  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

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})$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.