Efficient algorithms for vertical visibility problem

Question

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task:

The problem: we are given a two-dimensional square box of side $n$ whose sides are parallel to the axes. We can look into it through the top. However, there are also $m$ horizontal segments. Each segment has an integer $y$-coordinate ($0 \le y \le n$) and $x$-coordinates ($0 \le x_1 < x_2 \le n$) and connects points $(x_1,y)$ and $(x_2,y)$ (look at the picture below).

We would like to know, for each unit segment on the top of the box, how deep can we look vertically inside the box if we look through this segment.

Formally, for $x \in \{0,\dots,n-1\}$, we would like to find $\max_{i:\ [x,x+1]\subseteq[x_{1,i},x_{2,i}]} y_i$.

Example: given $n=9$ and $m=7$ segments located as in the picture below, the result is $(5, 5, 5, 3, 8, 3, 7, 8, 7)$. Look at how deep light can go into the box.

Fortunately for us, both $n$ and $m$ are quite small and we can do the computations off-line.

The easiest algorithm solving this problem is brute-force: for each segment traverse the whole array and update it where necessary. However, it gives us not very impressive $O(mn)$.

A great improvement is to use a segment tree which is able to maximize values on the segment during the query and to read the final values. I won't describe it further, but we see that the time complexity is $O((m+n) \log n)$.

However, I came up with a faster algorithm:

Outline:

1. Sort the segments in decreasing order of $y$-coordinate (linear time using a variation of counting sort). Now note that if any $x$-unit segment has been covered by any segment before, no following segment can bound the light beam going through this $x$-unit segment anymore. Then we will do a line sweep from the top to the bottom of the box.

2. Now let's introduce some definitions: $x$-unit segment is an imaginary horizontal segment on the sweep whose $x$-coordinates are integers and whose length is 1. Each segment during the sweeping process may be either unmarked (that is, a light beam going from the top of the box can reach this segment) or marked (opposite case). Consider a $x$-unit segment with $x_1=n$, $x_2=n+1$ always unmarked. Let's also introduce sets $S_0=\{0\}, S_1=\{1\}, \dots, S_n=\{n\}$. Each set will contain a whole sequence of consecutive marked $x$-unit segments (if there are any) with a following unmarked segment.

3. We need a data structure that is able to operate on these segments and sets efficiently. We will use a find-union structure extended by a field holding the maximum $x$-unit segment index (index of the unmarked segment).

4. Now we can handle the segments efficiently. Let's say we're now considering $i$-th segment in order (call it "query"), which begins in $x_1$ and ends in $x_2$. We need to find all the unmarked $x$-unit segments which are contained inside $i$-th segment (these are exactly the segments on which the light beam will end its way). We will do the following: firstly, we find the first unmarked segment inside the query (Find the representative of the set in which $x_1$ is contained and get the max index of this set, which is the unmarked segment by definition). Then this index $x$ is inside the query, add it to the result (the result for this segment is $y$) and mark this index (Union sets containing $x$ and $x+1$). Then repeat this procedure until we find all unmarked segments, that is, next Find query gives us index $x \ge x_2$.

Note that each find-union operation will be done in only two cases: either we begin considering a segment (which can happen $m$ times) or we've just marked a $x$-unit segment (this can happen $n$ times). Thus overall complexity is $O((n+m)\alpha(n))$ ($\alpha$ is an inverse Ackermann function). If something is not clear, I can elaborate more on this. Maybe I'll be able to add some pictures if I have some time.

Now I reached "the wall". I can't come up with a linear algorithm, though it seems there should be one. So, I have two questions:

• Is there a linear-time algorithm (that is, $O(n+m)$) solving the horizontal segment visibility problem?
• If not, what is the proof that the visibility problem is $\omega(n+m)$?

Answer 1

1. First sort both $x1$ and $x2$ coordinates of the lines in two seperate arrays $A$ and $B$. $O(m)$
2. We also maintain an auxilary bit array size $n$ to keep track of the active segments.
3. Start sweeping from the left to right:
4. for $(i=0,i<n,i++)$
5. {
6. ..if $\exists x1=i$ with $y$ value $c$ $O(1)$
7. ..{
8. ....find($\max$)
9. ....store($\max$) $O(1)$
10. ..}
11. ..if $\exists x2=i$ with $y$ value $c$ $O(1)$
12. ..{
13. ....find($\max$)
14. ....store($\max$) $O(1)$
15. ..}
16. }

find($\max$) can be implemented using an bit array with $n$ bits. Now whenever we remove or add an element to $L$ we can update this integer by setting a bit to true or false respectively. Now you have two options depending on the programming language used and the assumption $n$ is relatively small i.e. smaller than $long long int$ which is at least 64 bits or a fixed amount of these integers:

• Get the least significant bit in constant time is supported by some hardware and gcc.
• By converting $L$ to an integer $O(1)$ you will get the maximum (not directly but you can derive it).

I know this is quite a hack because it assumes a maximum value for $n$ and hence $n$ can be seen as a constant then...

Answer 2

I don't have a linear algorithm, but this one seems to be O(m log m).

Sort the segments based on the first coordinate and height. This means that (x1, l1) always comes before (x2, l2) whenever x1 < x2. Also, (x1, l1) at height y1 comes before (x1, l2) at height y2 whenever y1 > y2.

For every subset with the same first coordinate, we do the following. Let the first segment be (x1, L). For all other segments in the subset: If the segment is longer than the first, then change it from (x1,xt) to (L, xt) and add it to the L-subset in the proper order. Otherwise drop it. Finally, if the next subset has a first coordinate less than L, then split the (x1,L) to (x1, x2) and (x2, L). Add the (x2, L) to the next subset in the correct order. We can do this because the first segment in the subset is higher and covers the range from (x1, L). This new segment may be the one which covers (L, x2), but we won't know that until we look at the subset which has first coordinate L.

After we run through all of the subsets, we will have a set of segments which don't overlap. To determine what the Y value is for a given X, we only have to run through the remaining segments.

So what is the complexity here: The sort is O(m log m). Looping through the subsets is O(m). A lookup is also O(m).

So it seems that this algorithm is independent of n.