Exercise 8.16

Let S be a set of n segments in the plane. A line l that intersects all segments of S is called a transversal or stabber of S.

• Give an O(n^2) algorithm to decide if a stabber exists for S.
• Now assume that all segments are vertical. Give a randomized algorithm with O(n) expected running time that decides if a stabber exists for S.