平面(R^2)上の点集合の下側凸包を計算することは、計算幾何学における重要な問題であり、コンピュータグラフィックス、ロボット工学、地理情報システムなどの分野に応用されている。この問題を解くのに使えるアルゴリズムはいくつかあり、それぞれに長所と短所がある。ここでは、最も一般的な方法をいくつか、実行時の複雑さとともに紹介します：

グラハム・スキャン：これは2次元の点の集合の凸包を計算する古典的なアルゴリズムである。これは、点をx座標でソートし、左端の点から始めて、現在の外皮と左旋回を形成する点のみを残すことで動作する。このアルゴリズムの時間計算量は O(n log n) である。

Jarvis March (Gift Wrapping Algorithm)：これも2次元の凸包問題を解く古典的アルゴリズムである。このアルゴリズムは、左端の点から開始し、現在の外殻と右旋回を形成する次の点を繰り返し選択する。このアルゴリズムの時間的複雑度は O(nh) であり、ここで n は集合中の点の数、h は凸包上の点の数である。

Chanのアルゴリズムこれは，より効率的な解を提供するために，GrahamのスキャンとJarvis Marchの特徴を組み合わせた，より現代的なアルゴリズムである．このアルゴリズムの計算量は O(n log h)であり， n は集合中の点の数， h は凸包上の点の数である．

分割統治（Divide and Conquer）: このアルゴリズムは、凸包問題を解くために分割統治（Divide and Conquer）アプローチを用いる。入力点を2つに分割し、それぞれの凸包を計算した後、 2つの凸包をマージして最終解とする。このアルゴリズムの計算時間は O(n log n) である。

結論として、これらのアルゴリズムにはそれぞれ長所と短所があり、どれを使うかは、手元の問題の具体的な要件に依存する。例えば、Grahamのスキャンは小さなデータセットに対してシンプルで効率的な解法であり、Chanのアルゴリズムは凸包上の点の数が少ない大きなデータセットに対して良い選択である。
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.