Now, let us discuss how the convex hull of a planar point set can be constructed. The first method we will propose is a so-called naive algorithm. A naive algorithm seeks to solve a problem using the most obvious ideas and observations, thereby paying no attention to its computational complexity. While naive algorithms hardly find any applications in practice, they may be used, for example, to demonstrate that a problem can be solved in polynomial time. For our part, we will make use of the naive algorithm for computing the convex hull of planar points set. First to demonstrate its polynomial suitability and second to bring to light a number of issues that arise when we solve geometric problems and can embarrass geometric calculations and hinder geometric algorithms. Because of that, we should always be kept in mind by algorithm developers and programmers. Let P be the set of N points in the plane. For now let us assume that no three points from P are collinear or lie on the same line. The first observation we are going to make it the following. Two points from the set P define an edge of the convex hull, if and only if all the other points from P lie on the same side from the line through this segment. For example, in the figure you now see on the slide, the segment AB represents an edge of the convex hull. But, the segment AC you see now is not an edge of the convex hull because two points from P lie on one side of the line through A and C and seven points from P lie on the other side of the slide. The acceleration would have made immediately leads to the following algorithm. Let E denote a set that will store the edges of the convex hull. First, we initialize E with an implicit. Subsequently, for each ordered pair, AB, of points from P, we check whether all the other points from P lie on the left of the direct line through the points A and B, and if this is the case, we place the segment AB in the set E, and as a final set, we generate from the set E a list of vertices of the convex hull of our point set P. The algorithm spends linear time per each pair of points. The total number of pairs of points is quadratic. The last step can be easily accomplished in an algorithm and time. Hence, we summarize all that, we conclude that the time complexity of our algorithm is cubic in the number of points in the set P. Now, let us eliminate the non-degeneracy assumption that allows no three points from P to be collinear. We will adopt to the following convention. If for some edge of the convex hull, there is a point in P lying inside this edge, it is not classified as a vertex of the convex hull. As we should have expected, the naive algorithm has certain drawbacks. First, it is obviously too slow. But, even a more serious drawback is that it is not robust. Let us illustrate this point. Because of computational precision errors, we may get a set of segments E, which computatively represent convex hull edges, but in reality it may be impossible to assemble a polygon boundary from those segments. The figure on the left illustrates such variation. As you can see in this example to redundant adjacent edges were generated from a triple of almost collinear points, and it is obvious that from the eight segments shown in this figure, we cannot assemble a polygon boundary. Alternatively, central agents may be missed. For the same triple of almost collinear points, it might have happened that none of these three segments they defined was recognized as the convex hull edge, and if this happens, once again we will be left with a set of segments that cannot give rise to polygon boundary, and if you're particularly unlucky, we may even end up with an empty set E. Meaning that how you spent quite a bit of time on attempting to generate the convex hull edges, we are now left exactly with the same geometric configuration we have started with. An example of such a situation you can see in this slide. Even though such extreme cases are unlikely to often occur in practice, related issues should be anticipated, and they may cause us lots of headache. Therefore, we should definitely invest and afford in developing a faster and robust method for computing a convex hull for a planar points set.