18
$\begingroup$

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.

Seven segments; the shaded part indicates the region which can be reached by light

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)$?
$\endgroup$
  • $\begingroup$ How fast do you sort your m segments? $\endgroup$ – babou Aug 28 '14 at 22:22
  • $\begingroup$ @babou, the question specifies counting sort, which as the question says, runs in linear time ("linear time using a variation of counting sort"). $\endgroup$ – D.W. Aug 29 '14 at 4:50
  • $\begingroup$ Did you try sweeping from the left to right? All you need is sorting on $x1$ and $x2$ both in $O(m)$ and $O(m)$ steps to walk to the right. So in total $O(m)$. $\endgroup$ – invalid_id Aug 29 '14 at 12:15
  • $\begingroup$ @invalid_id Yes, I tried. However, in this case the sweep line must react appropriately when it meets the beginning of the segment (in other words, add the number equal to segment's $y$-coordinate to the multiset), meets the end of the segment (remove an occurence of $y$-coordinate) and output the highest active segment (output maximum value in the multiset). I have not heard of any data structures letting us do this in (amortized) constant time. $\endgroup$ – mnbvmar Aug 29 '14 at 15:43
  • $\begingroup$ @mnbvmar maybe a dumb suggestion, but how about an array of size $n$, the you sweep and stop every cell $O(n)$. For evry cell you know max $y$ and you can enter it in the matrix, furthermore you can keep track of the overall maximum with a variable. $\endgroup$ – invalid_id Aug 30 '14 at 7:51
1
$\begingroup$
  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...

$\endgroup$
  • $\begingroup$ As I see, assuming you have got 64-bit x86 processor, you are able to handle only $n \le 64$. What if $n$ is in the order of millions? $\endgroup$ – mnbvmar Sep 1 '14 at 7:47
  • $\begingroup$ Then you'll need more integers. With two integers you can handle $n$ up to 128, etc. So the $O(m)$ maximum finding step is hidden in the number of integers required, which you might still optimize if $m$ is small. You mentioned in your question that $n$ is relatively small so I guessed it is not in the order of millions. By the way long long int is always at least 64bits by definition even on a 32-bit processor. $\endgroup$ – invalid_id Sep 1 '14 at 7:52
  • $\begingroup$ Of course it is true, C++ standard defines long long int as at least 64-bit integer type. However, won't it be that if $n$ is huge and we denote the word size as $w$ (usually $w=64$), then each find will take $O\left(\frac{n}{w}\right)$ time? Then we would end up with total $O\left(\frac{mn}{w}\right)$. $\endgroup$ – mnbvmar Sep 1 '14 at 8:11
  • $\begingroup$ Yes, unfortunately for big values of $n$ that is the case. So now I wonder how big $n$ will be in your case and whether it is bounded. If it is indeed in the order of millions this hack-around will not work anymore, but if $c\cdot w\geq n$ for low $c$ values it will be fast and practically $O(n+m)$. So the best algorithm choice is, as usual, input dependent. For example for $n\leq 100$ insertion sort is normally faster then merge sort, even with a running time of $O(n^2)$ compared to $O(n \log n)$. $\endgroup$ – invalid_id Sep 1 '14 at 8:23
  • 3
    $\begingroup$ I am confused by your choice of formatting. You know you can typeset code here, right? $\endgroup$ – Raphael Sep 1 '14 at 10:51
0
$\begingroup$

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.

$\endgroup$

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.