How can one efficiently compute the lower convex hull of a set of Points P in the plane (R^2)? List potential approaches and analyse their runtime complexity.
Computing the lower convex hull of a set of points in the plane (R^2) is an important problem in computational geometry, with applications in areas such as computer graphics, robotics, and geographic information systems. There are several algorithms that can be used to solve this problem, each with its own advantages and disadvantages. Here are some of the most common methods, along with their runtime complexity:

Graham's scan: This is a classic algorithm for computing the convex hull of a set of points in 2D. It works by sorting the points by their x-coordinate, then starting from the leftmost point and keeping only the points that form a left turn with the current hull. The time complexity of this algorithm is O(n log n), where n is the number of points in the set.

Jarvis March (Gift Wrapping Algorithm): This is another classical algorithm that solves the convex hull problem in 2D. It starts from the leftmost point and iteratively selects the next point that forms a right turn with the current hull. The time complexity of this algorithm is O(nh), where n is the number of points in the set and h is the number of points on the convex hull.

Chan's Algorithm: This is a more modern algorithm that combines the features of Graham's scan and Jarvis March to provide a more efficient solution. It has a time complexity of O(n log h), where n is the number of points in the set and h is the number of points on the convex hull.

Divide and Conquer: This algorithm uses a divide and conquer approach to solve the convex hull problem. It divides the input points into two halves, computes the convex hulls of each half, and then merges the two hulls to form the final solution. The time complexity of this algorithm is O(n log n).

In conclusion, each of these algorithms has its own strengths and weaknesses, and the choice of which to use will depend on the specific requirements of the problem at hand. For example, Graham's scan is a simple and efficient solution for small datasets, while Chan's algorithm is a good choice for larger datasets with a small number of points on the convex hull.