Dear learners. Now we're starting the second week of our course on Computational Geometry. During this week, we will discuss the concept of the convex hull, arguably the most widely used geometric structure, and develop efficient algorithms for its computation. First of all, we need to introduce the definition of a convex set. A planar subset is convex if along with any two points, a and b, it contains the entire segment ab. In this figure, you see an example of a convex planar set. This planar set is not convex, since for the two its points labeled with a and b respectively, the red fragment of the segment ab lies outside this set. The convex hull is the fundamental geometric structure that has many applications in various scientific areas, including computer graphics, robotics, computer vision, image processing, and many others. Intuitively, it approximates a shape of complex objects with a simpler convex shape. On the left in this slide, you see an example. The respective non-convex set is the polygon having ten vertices, and its convex hull is given by a pentagon which is, of course, a simple structural. As another example, suppose we need to test for intersection, pairs of non convex polygons with many vertices. This task will be like a time consuming. However, instead we could first test for intersection of the convex hulls. Typically, this can be done much faster. And only if the answer for this test is positive, would we apply the complicated and time-consuming procedure. Now let us formally define convex hull for the case of a planar points set. Let P be a set of n points in the plane. The convex hull of P is the minimal convex set containing P. The convex hull of P is typically denoted by CH of P, which represents an abbreviation of the term convex hull. Note that here we mean minimality by inclusion. In other words, any convex set containing P also contains its convex hull. The figure you see on the left in this slide, illustrates this point. Alternatively, the convex hull of a planar points set P, can be defined at the intersection of all convex sets contained in P. However, both definitions are non-constructive and provide us with no way to actually compute the convex hull of a planar points set. In order to construct a convex hull, we will make use of the following observation. The convex hull of a planar point set P represents a convex polygon, with vertices at certain points from P. Finally, let us give the following intuitive interpretation of the convex hull of a planar point set. Let us take a nail at every point from P. Then, take an elastic rubber band and place it so that it will close all the nails, and afterwards let it go. The final shape it will take is that of the convex hull of the points set B.