[n]\times[n]における凸包の頂点数は\(O(n^{2/3})\)。ベクトル(i,j) (\(0 \leq i,j \leq m\)) を偏角の昇順に足すと、長さ\(\Theta(m^3)\)になる。i,jが互いに素な確率は\(1/\zeta(2)\)で近似できる（正確にはΦ関数で解析する必要があるが…）ので、頂点数が\Theta(m^2)、サイズ\Theta(m^3)のケースになる。

\(x_{i+1}=x_i+1-\lceil n/x_i \rceil\)で定義される点集合(i,x_i)の凸包の頂点数は \(O(n^{1/3})\)

a,bが垂直
\(\frac{a}{b}+\overline{(\frac{a}{b})}=0\)

z,a,bが同一直線上にある
\(\frac{z-a}{z-b}-\overline{(\frac{z-a}{z-b})}=0\)

垂心

単位円上の三点がなす三角形ABCの垂心は\(z=a+b+c\)と書ける。垂心と内心は一致する。
\(AZ \perp BC\) より
\begin{align}
&\frac{a-z}{b-c}+\overline{\left(\frac{a-z}{b-c}\right)} = 0 \\
\iff&(a-z)(1/b-1/c)+(1/a-\overline{z})(1/b-1/c)=0 \\
\iff&(a-z)(1/b-1/c)+(1/a-\overline{z})(b-c)=0 \\
\iff&-(a-z)+bc(1/a-\overline{z})=0 \\
\end{align}
同様に \(BZ \perp CA\) から得られる式を辺辺で引くと \(z=a+b+c\) を得る。これが元の式を満たすことは簡単に確かめられる。

同一直線上にない4点A,B,C,Dが同一円周上にあるための条件は
(a-b)/(c-b)÷(a-d)/(c-d)が実数であること。

最小包含円

3分探索
点を一つずつ増やしながら逐次最小包含円を求める方法もある。k点のときに最小包含円が更新される確率は高々3/kで、作り直すのに必要な時間はO(k)なので、平均O(n)で動作する。
2次元平面上のN個の点について、遠い方からk個の点までの距離の和を最小化する点を見つけよ（https://onlinejudge.u-aizu.ac.jp/problems/2972）。
凸関数のmaxは凸関数。k個大きい方から取ってくるのは max_|S|=k f と書けるので凸関数で、三分探索。

二次元平面上のN点が与えられる。ここから、凸k多角形を選んで、内部に含まれる点の個数を答えよというクエリが与えられる。これは、積分によって、前計算O(n^3)の下、各クエリO(k)で答えられる。線分の下にある点の個数を前計算する。

ボロノイ図の一番外側のセルは凸包によって求まる（AGC021B）

双対
点p=(a,b)の双対を直線y=ax+bとして定義して、p*と置く。垂直な直線の双対は存在しないことに注意。

点p,qを通る直線lは直線p*,q*の交点l*に移る。lの上側にある点zはl*の上側の直線z*に移る。n個の点が与えられる。各二点を通る直線の上側にある点の個数の数え上げは、双対をとることで、直線の下側にある点の数え上げになり、O(n)で計算できる。双対を戻すと、各点ごとに、その点を通る直線を偏角順に走査している。偏角順に並べるのは、各直線について、同じ点を通り、角度がもっとも近いものをO(n)で列挙すれば、O(n^2)でてきる。凸包の双対は包絡線になる。

ドロネー三角形
角度の列が辞書順最小になるような分割。ドロネー三角形に含まれる三角形ABC,三角形ABDを考える。ABをflipして、辞書順が小さくなるなら定義よりにドロネー三角形ではない。これは、A,B,Cを通る円の内部にDが含まれず、A,B,Dを通る円の内部にCが含まれないことと同値。逆に、そのような違反辺がなければドロネー三角形であることが知られている。より強く、三角形化の任意の三角形について、その三点を通る円の内部に他の点がないこととドロネー三角形であることが同値であることが言える。
ユークリッド最小全域木はドロネー三角形の辺だけを使う。ABがEMSTの辺だとする。すると、ABを直径とする円内に他の点が含まれない。これは、凸四角形ABCDについて、A,B,Cを通る円の内部にDが存在しないことを意味している。
ボロノイ分割
一点ずつ点を追加して逐次、ボロノイ図を作ると、O(n^2)で構成できる。
凸包
二つの交わらない凸包が与えられたとき、その二つの接線は尺取り法により線形で求まる。これにより、二つの凸包の凸包が線形で求まる。

(x,y,x^2+y^2)の凸包のxy平面への射影がボロノイ分割になる。三次元凸包は分割統治によりO(nlogn)で求まる。

N点が与えられる。bounding boxの種類数をO(n^2 log n)て求めよ。https://csacademy.com/contest/round-36/task/bbox-count/

最近接二点対

乱択O(n)
一点ずつ逐次処理してその時点での最近接2点対を見つける。その時点での最近接距離をδとする。長さδ/2の正方形で領域を分割する。新たに点が追加されたとき、その点の周りの9×9個の正方形だけチェックすればよい。最近接距離が更新される確率は点数kに対してO(1/k)、正方形領域を作り直すのにO(k)なので合計で平均O(n)になる。

距離K以下の点対をすべて求めよ（ABC234Ex）。
AB \leq (A^2+B^2)/2

3次元の点がN個与えられる。LISをO(n log n)で求めよ。

N個の直線が与えられる。原点からK番目に近い交点の距離を求めよ(ABC263H)。

マンハッタン距離のハミルトン閉路で、長さ最大のものを求めよ。

3色で塗り分けられたN点が与えられる。それぞれK個まで削除できる。それぞれ交わらないbounding boxを作れるか。

だんだん大きくなる円がいくつかある。移動速度が与えられる。点sからtへ円に触れずに移動できるか。geocon2013_d

反転幾何

凸多角形の辺上を速度xで、内部を速度yで動ける。sからtに移動するときの、移動時間を求めよ。

Aoj2016

y = ax + b (a, b ∈ Z) による包絡線は凸包の応用で求まる(ARC130F)。