Consider the sweep-line algorithm for a set S = fs1 : : : sng of n segments (not necessarily horizontal or vertical). Assume that you stopped the algorithm once an intersecting pair is found. There are n(n1)=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 si 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.