平面上の点集合の下側凸包を計算するアルゴリズムはいくつかあり、実行時の複雑さと実装の容易さの点で異なるトレードオフがある。ここでは，最もよく使われるものをいくつか紹介する．

    アンドリューのアルゴリズム：これは掃引線アルゴリズムで、点をx座標でソートし、単調連鎖を維持しながら左から右に点をスキャンする。単調連鎖はバイナリサーチを使って更新され、O(log n)の時間がかかる。このアルゴリズムの全体的な時間複雑度はO(n log n)である。

    グラハム・スキャン（Graham's Scan）：これはもう一つの掃引線アルゴリズムで、左端の点を基準とした極角で点をソートする。このアルゴリズムは、点を順番にスキャンし、凸角でない角度を作る点をスタックから取り除く。このアルゴリズムの時間複雑度はO(n log n)である。

    Chanのアルゴリズム：これはGrahamのスキャンを改良したもので、分割統治アプローチを使って極角で点をソートする。このアルゴリズムはO(n log n)の時間を要し、Grahamのscanよりも優れた定数係数を持つので、大きな入力に対して実際に高速である。

    Jarvis March (Gift Wrappingとしても知られる)：これは、左端の点から開始し、現在の外皮に最も近い点を繰り返し見つけるインクリメンタルなアルゴリズムである。このアルゴリズムは最悪の場合O(n^2)の時間を要するが、最も近い点を見つけるためにバイナリ探索木を使用することで、O(n log n)の時間を要するように最適化することができる。

    QuickHull：これは分割統治アルゴリズムであり、極点（左端、右端、最上位、最下位の点）を見つけることから始め、点の集合を2つの凸包に再帰的に分割する。このアルゴリズムの時間計算量は、平均でO(n log n)、最悪の場合でO(n^2)である。

効率という点では、最も効率的なアルゴリズムはAndrew's、 Graham's、Chan'sであり、その時間複雑度はO(n log n)である。Jarvis MarchとQuickHullアルゴリズムも実行可能な選択肢ですが、最悪の場合の時間複雑度はO(n^2)と高くなります。
There are several algorithms to compute the lower convex hull of a set of points in the plane, with different trade-offs in terms of runtime complexity and ease of implementation. Here are some of the most popular ones:

    Andrew's Algorithm: This is a sweep line algorithm that sorts the points by their x-coordinate, and then scans the points from left to right while maintaining a monotone chain. The monotone chain is updated using binary search, which takes O(log n) time, where n is the number of points in the chain. The overall time complexity of the algorithm is O(n log n).

    Graham's Scan: This is another sweep line algorithm that sorts the points by their polar angle with respect to the leftmost point. The algorithm then scans the points in order, and removes points from the stack if they create a non-convex angle. The time complexity of the algorithm is O(n log n).

    Chan's Algorithm: This is an improvement on Graham's scan that uses a divide-and-conquer approach to sort the points by their polar angle. The algorithm takes O(n log n) time, and has a better constant factor than Graham's scan, which makes it faster in practice for large inputs.

    Jarvis March (also known as Gift Wrapping): This is an incremental algorithm that starts from the leftmost point and repeatedly finds the point that is closest to the current hull. The algorithm takes O(n^2) time in the worst case, but can be optimized to take O(n log n) time by using a binary search tree to find the closest point.

    QuickHull: This is a divide-and-conquer algorithm that starts by finding the extreme points (the leftmost, rightmost, topmost, and bottommost points), and then recursively divides the set of points into two convex hulls. The time complexity of the algorithm is O(n log n) on average, and O(n^2) in the worst case.

In terms of efficiency, the most efficient algorithms are Andrew's, Graham's and Chan's, with a time complexity of O(n log n). The Jarvis March and QuickHull algorithms are also viable options, but their worst-case time complexity is higher, at O(n^2).