Let {h...hm} be a set of half-planes, all containing (0,00). Furthermore, assume that the are given in increasing order of slopes, as in Figure 1. In class we saw how we can compute Cn=hi nhun....hn in time O(n log n). Suggest an algorithm that in worst case time O(n) computes Cm=hi nhan...hm. Hint: remind yourself how Graph Scan works. hi ho hs. ha ns Figure 1: Input for question The output should be the dotted polygonal path Let {h...hm} be a set of half-planes, all containing (0,00). Furthermore, assume that the are given in increasing order of slopes, as in Figure 1. In class we saw how we can compute Cn=hi nhun....hn in time O(n log n). Suggest an algorithm that in worst case time O(n) computes Cm=hi nhan...hm. Hint: remind yourself how Graph Scan works. hi ho hs. ha ns Figure 1: Input for question The output should be the dotted polygonal path