直線 $y = ax + b$ を点 $(a, b)$ に関連づける双対を考えましょう。
詳しいことはこちらの動画をご覧ください 👉 https://www.youtube.com/watch?v=UYicZQGmc5E&list=PLMDFPuH4ZxUGe-qreA6cde5g7PywDvrsD&index=10
Convex Hull Trick
直線族の各点最小値に興味があるタイプの Convex Hull Trick を考えましょう。
直線 $l _ 0, l _ 1, l _ 2$ が左から「無駄なく」並んでいる条件は、傾きが狭義単調減少でかつ $l _ 1 < l _ 0 \cap l _ 2$ （ただし直線と点を不等号で結んだらそれは点の $x$ 座標における $y$ 座標を比較しましょうという意味とします）が成り立っていることですね。
双対を取ると $l _ 0 ^ \ast, l _ 1 ^ \ast , l _ 2 ^ \ast$ の $x$ 座標が狭義短調増加でかつ、$l _ 0 ^ \ast l _ 2 ^ \ast < l _ 1 ^ *$、すなわち $\mathtt{orient2d}(l _ 0 ^ \ast , l _ 1 ^ \ast , l _ 2 ^ \ast) > 0$ と言い換えることができて、これはすぐに実装できるわけです。
これで凸包問題に言い換えることができていることにも注意ですね。
凸共役性（Legendre–Fenchel transformation）との関連
凸関数 $f: \mathbb{R} → \mathbb{R} \cup \lbrace + \infty \rbrace$ を、次のように定義される別の関数 $f ^ \ast$ に移す双対を考えます。
$$ f ^ \ast ( p ) = \sup \lbrace p x - f(x) : x \in \mathbb{R} \rbrace $$
詳しいことはこれは動画ではありませんがみなさまが頭をグイングインです 👉 凸共役性 - Wikipedia
さて、直線 $y = ax + b$ の凸共役を考えましょう。それは点 $a$ において値 $-b$ をとり、それ以外の点では $+\infty$ を取るものです。これは $y$ 座標の符号が逆であることを除けば点 $(a, b)$ に対応しているとみることができるでしょう。もちろん $y$ 座標の符号は些細な定義の流派の問題ですが、計算幾何の文脈と凸解析の文脈で、習慣となっている符号が互いに逆なのですよね。
