[MUSIC] Our present goal is to develop a first and robust algorithm for computing a context hull of a planar point at p. First, let's introduce the notions of the upper and lower hull, we will make use of thereby. For now, let's assume that no two points from the set p lie on the same vertical line or equivalently have the same x coordinate. The upper hull of a point set p represents the upper polygonal chain cut out of the boundary of the context hull of P. With the end points and the leftmost and rightmost vertices of the context hull. In the example on the left, the leftmost and rightmost vertices of the context hull are highlighted in green. And the upper hull of the point set P is highlighted in red. The lower hull of the point set P is defined analogously. And thus, it represents the lower polygonal chain cut out of the boundary of the context hull of P, with the endpoints at the leftmost and rightmost vertices of thecontext hull. In the figure you see in this slide, the lower hull of the set p is highlighted in blue. Now we will describe in detail a fast and robust method for computing the upper hull of planar points at P. Which is known as Modified Graham's algorithm, [INAUDIBLE] the lower hull can be reconstructed an algorithm. Let L upper denote a list that will store the list of the upper hull. At the very beginning, we initialize L upper with an empty set. Further, we sort the points from p by the increasing x coordinate. Subsequently, we iterate over all the remaining points from p. When processing the next point, we first append it to the end of the list L upper. Further, while the list L upper contains three or more points, we iteratively check whether the last three points do not form a right turn. And if this is the case, we eliminate from L uuper the second last point. After the last and namely the rightmost point from p is processed, the list L upper will store the vertices of the upper hull of p ordered by the increasing x coordinate. Let us follow step by step construction of the upper hull for a sample set of 11 points, you see in this slide. The labeling of the points is consistent with their ordering by the x coordinate. In particular, the leftmost point is labeled as p1, and the rightmost one as p11. At the time of initialization would place the points p1 and p2 in the list L upper. Next, the point p3 is examined, and since the points p1, p2, and p3 make a right turn, we proceed to the point before. Haven't we been to the point before to L upper, we notice that the last three points in the last, and namely, p2, p3, and p4 form a left turn. And consequently, we eliminate from the list the point p3. Now, L upper contain the points p1, p2, and p4, and we proceed to the point P5. After the point p5 is appended to the list, the last three vertices is stored in it and named it p2, p4, and p5, again, make a left turn. And thus, we need to eliminate the point p4. Now the list L upper contains the point, p1, p2, and p5. Further, we consecutively append to the list the point p6 and then p7. After in this step, the last three points in the list L upper make a right turn, but after I append to the list the point p8. Once again, we are facing a situation when the last three point from a left turn. And because of that, we consecutively eliminate the point p7, then p6, and then p5. Afterwards, the list L upper contains only three points, namely p1, p2, and p8. Further, we can safely append to the lists the point p9 then p10. And finally, the last point from our set, p11. This last action leads to consecutive elimination from the list of point p10 and then p9. So finally, we are left with the list L upper storing four points and namely p1, p2, p8, and p11. These upper side of the points that represent the vertices of the upper hull of the points at p. Now let us describe a way of properly handling degenerate cases. Suppose that some points from the set p may lie on the same vertical line. Let us agree that when installing the point from p, we alter them lexicographically. This means that the point p is considered smaller than the point q if either of their x coordinate of p is smaller than their of q. Or p and q have the same x coordinate, but the y coordinate of p is smaller than that of q. In the example, you see on the left in the slide, there are three points. The point labelled by 1 lies to the left of those labelled by 2 and 3 respectively. The points 2 and 3 lie on the same vertical line, and in particular, the point labeled by 2 lies below the point labeled by 3. Consequently, this labeling is consistently with this lexicographical ordering of these three points. Note, that we no longer need to worry whether the set p might contain three colinear or almost collinear points. If like in the example in this slide, there are three such points, a, r and b that potentially can give rise either to a single edge, ab, of the upper hull or to two adjacent edges ar and rb. Of course, we still can make our own decision. To make this more precise, incase r is to assumed to lie below the segment ab, then only edge ab will be introduced. And if the point r is supposed to lie above the segment ab, then two edges ar and rb will be generated. Either decision may turn out to be wrong, yet in either case, the output of our algorithm will represent a polygonal chain with the endpoints at the leftmost and rightmost vertex of the context hull respectively. Which are the leftmost and rightmost point from the set p respectively. And the polygon chain we obtain will closely approximate the upper hull of the set p of points. In fact, the approximation we obtained will be good enough, so that we won't be able to distinguish it from the correct upper hull. And this means that what we have obtained is perfectly suitable from the point of view of our needs. It remains to analyze the time and space complexity of our algorithm. Sorting by x coordinate of the points from p can be done in n logarithm n time. Initialization of the list L upper is performed in constant time. A single iteration of the for-cycle may take linear time, since a linear number of points may need to be deleted from the list L upper. However, note that prior to being deleted, a point needs to be inserted into the list L upper. And being once deleted from it, it will never reappear in L upper again. Therefore, the total number of deletion will be linear in n. This implies that the entire time spent in the for-cycle is linear in n as well. We conclude that the modifier Graham's algorithm runs in n logarithm n time. And requires linear space since that most endpoints can be stored simultaneously in the list L upper. It can be shown that these time and space estimates are worst case optimal for the problem under consideration.