ギフト包装法
ここでは話を簡単にするため、どの3点も一直線上にないとする。一直線上にある場合は、最も遠い点を選ぶか、凸包の辺上の全ての点を選べば良い。また、実装を完璧にするには、点が2つ以下の場合も取り扱う必要がある。
凸包に必ず含まれていることが確実な点 P 0 {\displaystyle P_{0}} から始める。この点は例えば一番左端の点を選べば良い。そして、 P i + 1 {\displaystyle P_{i+1}} は全ての点が直線 P i P i + 1 {\displaystyle P_{i}P_{i+1}} の右側にあるように選べば良い。この点は P i {\displaystyle P_{i}} を基点にした偏角を比較することで計算量 O(n) で求まる。そして、 P h = P 0 {\displaystyle P_{h}=P_{0}} となるまで、これを反復する。
この方法は3次元以上でも同様にできる。