[Solved]: Finding the point nearest to the x-axis over some segment

Problem Detail: 

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.

Asked By : com

Answered By : edA-qa mort-ora-y

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2101

3.2K people like this

 Download Related Notes/Documents