凸境界・半平面制約を扱う
概要
向きと交差を判定できた後、点集合を凸包へ絞る方法と、半平面の共通部分として実行可能領域を表す方法を学ぶ。直線群の最小値・最大値queryは直線包絡の単元で扱う。
考え方
領域が凸であるとは、その中のどの二点を選んでも、二点を結ぶ線分がすべて領域に含まれることである。まず、正方形 、すなわち を考える。この領域は、四つの半平面 の共通部分である。一つの一次不等式は直線の片側を表し、すべての不等式を満たす点だけが実行可能な点として残る。
この正方形上で線形目的関数 を最大化する。 と より値は 以下であり、頂点 で実際に となる。値を一定にする直線 を、値が増える方向 へ平行に動かすと、最後に領域へ触れるのが である。領域全体を片側に置いたまま境界に触れるこの直線を支持直線、最大値を取る点をその方向の支持点と呼ぶ。
頂点を調べればよい理由は、単に図の端に見えるからではない。有界な凸多角形の各点は、頂点の座標を非負の重みで、重みの合計が になるように足して表せる。線形目的関数の値も頂点での値の同じ重み付き平均になるため、最大の頂点値を超えない。したがって、頂点の中に最大値を達成する点がある。目的が だけなら右側の辺上の全点が最適になるが、その場合も端の頂点を一つ選べる。
点が入力される場合は、それらを含む最小の凸集合である凸包を作り、支持方向ごとに必要な境界候補を調べる。凸包・支持方向・境界候補ではその構築と探索を学ぶ。制約が入力される場合は、上の正方形と同じく「各半平面を同時に満たすか」から始め、半平面制約・凸領域の共通部分へ進む。包含判定だけなら、共通部分の頂点を実際に作らずに済む場合もある。
成立条件と計算量
線形目的関数の最大・最小を頂点で達成できるという説明は、ここでは空でない有界な閉じた凸多角形を前提とする。最小化は目的関数の符号を反転すれば最大化へ直せる。非有界な領域では最適値自体が存在しない場合もあり、この結論をそのまま使わない。
また、同じ正方形でも、凸関数
を最小化するなら答えは内部の での である。二つの二乗はともに非負で、この点では両方が となる。一方、四頂点での値はすべて 、境界上の最小値も なので、境界だけに絞ると最適解を失う。「領域が凸だから」という理由だけで候補を削らず、目的関数と最大化・最小化のどちらを行うかを確かめる。
計算量も入力の表現で変わる。 点の静的な凸包構築は整列を含めて 時間、 空間で行える。半平面が 本なら、一点が全条件を満たすかの直接判定は 時間だが、共通領域そのものを構築する費用とは異なる。子単元では、保持する境界と必要な問合せを定めてから全体の費用を数える。
ABC341 Gの公式解説は、区間平均を累積和の点を結ぶ傾きへ直し、上側の凸包で候補を絞る応用である。上の正方形の小例とは目的の式が異なるため、同問では「最大の傾きを与える点が上側の境界にある」理由を改めて確認する。
下位単元
- 凸包・支持方向・境界候補 — 青色
- 半平面制約・凸領域の共通部分 — 黄色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
導入対象の目安: 青色(1600–1999)。凸性によって内部の候補を捨て、境界と半平面で領域を表す入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 幾何・凸最適化。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-convex-geometry
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 直線群の最小値・最大値queryはConvex Hull Trick・直線包絡で扱う。凸性を使わない一般のevent sweepや座標圧縮も対象外とする。