Explain the concept of convex hull in Computational Geometry.

In computational geometry, the concept of convex hull refers to the smallest convex polygon that encloses a given set of points in a plane or in higher-dimensional space. It is a fundamental concept used in various applications such as computer graphics, pattern recognition, robotics, and geographic information systems.

A convex polygon is defined as a polygon in which any line segment connecting two points within the polygon lies entirely within the polygon. The convex hull of a set of points is the smallest convex polygon that contains all the points.

To understand the concept of convex hull, let's consider a set of points in a plane. The convex hull of these points is the smallest convex polygon that encloses all the points. It can be visualized as wrapping an elastic band around the points such that it stretches to cover all the points while maintaining its convexity.

There are several algorithms to compute the convex hull of a set of points. One of the most commonly used algorithms is the Graham's scan algorithm. This algorithm works by first finding the point with the lowest y-coordinate (or the leftmost point in case of a tie) and using it as the starting point. Then, it sorts the remaining points based on their polar angles with respect to the starting point. The algorithm iteratively adds the points to the convex hull in a counterclockwise manner, discarding any points that create a clockwise turn. Finally, it returns the set of points that form the convex hull.

Another popular algorithm is the Jarvis march algorithm, also known as the gift wrapping algorithm. This algorithm starts with the leftmost point and iteratively finds the point that forms the smallest angle with the current point. It continues this process until it returns to the starting point, forming the convex hull.

The complexity of computing the convex hull depends on the algorithm used. The Graham's scan algorithm has a time complexity of O(n log n), where n is the number of input points. The Jarvis march algorithm has a time complexity of O(nh), where h is the number of points on the convex hull.

In conclusion, the concept of convex hull in computational geometry refers to the smallest convex polygon that encloses a given set of points. It is computed using various algorithms, such as Graham's scan and Jarvis march, and has applications in various fields.