Line Segments

Algorithm and Runtime

• S \(\leftarrow\) Stack
• For segment i by ascending x-coordinate: \(O(n)\).
  • Pop from S until the top element s can be hit by i or S is empty: RTP amortised \(O(1)\).
  • Emit index of s or 0 in the empty case: \(O(1)\).
  • Push i onto S: \(O(1)\).

To see that our pop-step is amortised \(O(1)\) we note that every element is pushed onto our stack at most one time. We can only pop as many elements as we push, so in total we can pop \(O(n)\) elements. Our loop runs \(O(n)\) times, so the amortised pop-step per iteration is \(O\left(\frac{n}{n}\right) = O(1)\). This guarantees overall \(O(n)\) runtime \(\square\).

Correctedness

1. If an element is popped at iteration \(i\) it was lower than interval \(i\). If it is lower than interval \(i\), any subsequent interval would have to pass through \(i\) to hit it. As such it cannot be the first-hit point for any subsequent interval.
2. The stack is populated in loop-order. This is ascending x-coord, so higher elements always have larger x-coordinates.

When we consider an interval, we keep on throwing away elements until we find one that we can hit. From (2), among all elements in the stack we can hit, this is the one with the largest x-coordinate. From (1), we throw away a value IFF we cannot use it later. As such, there can be no intervals that could possibly hit first that were not present in the stack. The proof is complete.