凸包・支持方向・境界候補
概要
内部点が線形/凸目的に不要なことを示し、orientation順で凸境界を構成して支持方向ごとの極値を得る。
考え方
点を辞書順に並べ、同じ向きの曲がりだけを残すstackで下側・上側の凸包を作る。線形目的の最大値なら内部点は境界点の凸結合以下なので候補から除ける。凸包を作る目的と、求める量の性質を結び付ける。
Andrew法では点を(x,y)辞書順にsort・uniqueする。下側のstackに点pを順に追加するとき、末尾二点a,bに対するcross(b−a,p−b)≤0の間bをpopし、最後にpをpushする。上側は逆順で同様に作り、両端の重複を除いてつなぐ。除いたbは新しい下側支持辺の上側または辺上にあり、下側凸境界の頂点になれない。各点が高々一回push・popされるため走査はO(N)。
辺上の全点を残す場合はpop条件を<0へ変えるが、全点共線では上下の連結で二重に出力しないよう別処理する。unique後0,1,2点も明示的に返す。線形目的a·pなら任意内部点p=Σα_i v_iに対してa·p=Σα_i a·v_i≤max_i a·v_i。凸目的の「最大」もJensenの不等式で同様だが、凸目的の最小は内部で達することがあり、凸包頂点だけへ絞れない。
支持方向に合わせた鎖の探索
静的点集合でAx+Byを最大化するなら、上下の鎖をx昇順に持ち、B>0では上側、B<0では下側を選ぶ。同じxには上側で最大y、下側で最小yだけを残す。上側の傾きは非増加、下側は非減少なので、選んだ鎖では隣接差Δx(A+B·傾き)の符号が正から非正へ一度だけ変わる。この符号境界を二分探索すれば支持点をO(log N)で得る。差はAΔx+BΔyで直接評価でき、傾きの除算は不要である。B=0はxの端点、A=B=0は0とする。
下側鎖(0,100),(1,−100),(2,−99),(3,−97),(4,0)のy値は谷型なので、方向(0,1)で最大化の単峰探索をする対象にはならない。凸包全周にも開始位置をまたぐ極値があるため、任意の頂点順を普通の単峰列とみなさない。向きと探索区間を定めてから単調性を証明する。
成立条件と計算量
N点でsortがO(N log N)、走査O(N)。重複点、全点共線、辺上の点を残すかを固定する。回転calipersの線形走査は支持点が単調に進む根拠を要する。任意の幾何目的が凸包だけで解けるわけではない。
問題一覧
- ABC341 G「Highest Ratio」 公式問題
- ABC275 G「Infinite Knapsack」 公式問題
- ABC286 Ex「Don't Swim」 公式問題
- ABC244 Ex「Linear Maximization」 公式問題
技能・出典
主題: 凸包・支持方向・境界候補(目的関数に対して内部候補が不要な理由を示し、凸境界だけを列挙できる。)。既習技能: Segment Treeのcanonical区間分解(区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。)。主タグ: 凸包・支持方向・境界候補 / 補助タグ: Segment Treeのcanonical区間分解
- ABC356 G「Freestyle」 公式問題
- ABC257 Ex「Dice Sum 2」 公式問題
技能・出典
主題: 凸包・支持方向・境界候補(目的関数に対して内部候補が不要な理由を示し、凸境界だけを列挙できる。)。既習技能: kinetic sorting・交差event順序更新(隣接要素が入れ替わる有効時刻だけをevent処理し、連続parameterに対する全順序と集計を更新できる。)。主タグ: 凸包・支持方向・境界候補 / 補助タグ: kinetic sorting・交差event順序更新
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。外積で凸包を構築し、支持方向と境界上の極値を扱う。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 凸境界・半平面制約を扱う。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-convex-boundary-hull
凸包・支持方向・境界候補
習得する技能
- 目的関数に対して内部候補が不要な理由を示し、凸境界だけを列挙できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 幾何の基本判定と座標変換。
このUnitを直接前提とする単元: なし。
幾何の基本判定・配置・座標変換で得た考え方と実装を再利用し、凸包・支持方向・境界候補の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 凸包・支持方向・境界候補の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。