凸境界・半平面制約を扱う

概要

向きと交差を判定できた後、点集合を凸包へ絞る方法と、半平面の共通部分として実行可能領域を表す方法を学ぶ。直線群の最小値・最大値queryは直線包絡の単元で扱う。

考え方

領域が凸であるとは、その中のどの二点を選んでも、二点を結ぶ線分がすべて領域に含まれることである。まず、正方形 [0,2]2[0,2]^2、すなわち 0≤x≤2, 0≤y≤20\leq x\leq 2,\ 0\leq y\leq 2 を考える。この領域は、四つの半平面 x≥0, x≤2, y≥0, y≤2x\geq 0,\ x\leq 2,\ y\geq 0,\ y\leq 2 の共通部分である。一つの一次不等式は直線の片側を表し、すべての不等式を満たす点だけが実行可能な点として残る。

この正方形上で線形目的関数 x+2yx+2y を最大化する。x≤2x\leq 2 と y≤2y\leq 2 より値は 66 以下であり、頂点 (2,2)(2,2) で実際に 66 となる。値を一定にする直線 x+2y=cx+2y=c を、値が増える方向 (1,2)(1,2) へ平行に動かすと、最後に領域へ触れるのが x+2y=6x+2y=6 である。領域全体を片側に置いたまま境界に触れるこの直線を支持直線、最大値を取る点をその方向の支持点と呼ぶ。

頂点を調べればよい理由は、単に図の端に見えるからではない。有界な凸多角形の各点は、頂点の座標を非負の重みで、重みの合計が 11 になるように足して表せる。線形目的関数の値も頂点での値の同じ重み付き平均になるため、最大の頂点値を超えない。したがって、頂点の中に最大値を達成する点がある。目的が xx だけなら右側の辺上の全点が最適になるが、その場合も端の頂点を一つ選べる。

点が入力される場合は、それらを含む最小の凸集合である凸包を作り、支持方向ごとに必要な境界候補を調べる。凸包・支持方向・境界候補ではその構築と探索を学ぶ。制約が入力される場合は、上の正方形と同じく「各半平面を同時に満たすか」から始め、半平面制約・凸領域の共通部分へ進む。包含判定だけなら、共通部分の頂点を実際に作らずに済む場合もある。

成立条件と計算量

線形目的関数の最大・最小を頂点で達成できるという説明は、ここでは空でない有界な閉じた凸多角形を前提とする。最小化は目的関数の符号を反転すれば最大化へ直せる。非有界な領域では最適値自体が存在しない場合もあり、この結論をそのまま使わない。

また、同じ正方形でも、凸関数

g(x,y)=(x−1)2+(y−1)2g(x,y)=(x-1)^2+(y-1)^2

を最小化するなら答えは内部の (1,1)(1,1) での 00 である。二つの二乗はともに非負で、この点では両方が 00 となる。一方、四頂点での値はすべて 22、境界上の最小値も 11 なので、境界だけに絞ると最適解を失う。「領域が凸だから」という理由だけで候補を削らず、目的関数と最大化・最小化のどちらを行うかを確かめる。

計算量も入力の表現で変わる。NN 点の静的な凸包構築は整列を含めて O(Nlog⁡N)O(N\log N) 時間、O(N)O(N) 空間で行える。半平面が MM 本なら、一点が全条件を満たすかの直接判定は O(M)O(M) 時間だが、共通領域そのものを構築する費用とは異なる。子単元では、保持する境界と必要な問合せを定めてから全体の費用を数える。

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や座標圧縮も対象外とする。

根拠