11. Consider the sweep-line algorithm for a set S {s1 ... Sn} of n segments (not...

Transcribed Image Text:

11. Consider the sweep-line algorithm for a set S {s1 ... Sn} of n segments (not necessarily horizontal or vertical). Assume that you stopped the algorithm once an intersecting pair is found. There are n(n-1)/2 pairs of segments. However the algorithm does not check every pair for intersection. Only pairs that are consecutive on the sweeping line are checked. If it costs one dollar to check if s; crosses sj, how many dollar (as as function of n) should you pay in the worst (most expensive) case ? Note that the same pair might be checked multiple times. Give a example of an input where there is a pair of segments si, 8; and the algorithm checks more than 17 times if they intersect. (the very same pair). 11. Consider the sweep-line algorithm for a set S {s1 ... Sn} of n segments (not necessarily horizontal or vertical). Assume that you stopped the algorithm once an intersecting pair is found. There are n(n-1)/2 pairs of segments. However the algorithm does not check every pair for intersection. Only pairs that are consecutive on the sweeping line are checked. If it costs one dollar to check if s; crosses sj, how many dollar (as as function of n) should you pay in the worst (most expensive) case ? Note that the same pair might be checked multiple times. Give a example of an input where there is a pair of segments si, 8; and the algorithm checks more than 17 times if they intersect. (the very same pair).