Minimum Enclosing Rectangle

二維平面的矩形，包圍所有點。可令面積最小、令周長最小。

凸包，旋轉卡尺。O(NlogN)。

UVa 819 10173 ICPC 5138

UVa 12307

Minimum Enclosing Box / Minimum Bounding Box

三維空間的長方體，包圍所有點，體積最小。

三維旋轉卡尺？正確性不明。O(N³)。

UVa 12308

Maximum Empty Rectangle

Largest Empty Rectangle among a Point Set. Jeet Chaudhuri, Subhas C. Nandy. 1999.

O(N³)。

Maximum Empty Axis-Parallel Rectangle

二維平面的矩形，不含任何點，矩形擺正，面積最大。

平面邊界四個角落補點，窮舉每一點當作矩形左（與右）邊界，然後依序掃描右方（與左方）的點作為右（左）邊界，掃描過程中隨時更新上下邊界。另外，矩形的左右邊界可能是平面的左右邊界。O(N²)。

Divide-and-Conquer Method。O(Nlog³N)。

UVa 10043

Minimum Enclosing Square Annulus

二維平面的方環，包圍所有點。可令寬度最小、令面積最小。

ICPC 6121

Maximum Weight Axis-aligned Rectangle

二維平面上有許多點，每個點有權重，有正有負。找到一個擺正的矩形，內部所有點的權重總和最大。

O(N²)。

Minimum Enclosing Circle

二維平面的圓，包圍所有點，面積暨周長暨半徑最小。

一個圓包圍所有點，半徑相對伸縮後，一個點歸屬所有圓。

圓心位於Farthest Point Voronoi Diagram頂點。O(NlogN)。

Randomized Incremental Method。平均O(N)，最差O(N²)。

以遞增法求最小包圍圓，逐次添加一點，並且調整最小包圍圓。若新點在圓內，不做任何事；若新點在圓外，則新點一定在新圓上，但是本來的點就不一定在新圓上了。於是得到新問題：已知一點在圓上，求最小包圍圓。接著又得到新問題：已知兩點在圓上，求最小包圍圓。已知兩點時，以枚舉法掃描所有點，找到最遠的點。

添加一點的時間複雜度分成兩種情況：圓不變、圓變動。因為無法預測變動，所以窮舉各種結果、反推變動機率。各種結果是新圓上有兩點、有三點。現有i點、已知一點在圓上，因此新點導致新圓的機率是(2-1)/i、(3-1)/i。添加一點的平均時間複雜度是O(1)，添加N點的平均時間複雜度是O(N)。原始問題以此類推，平均時間複雜度O(N)。

UVa 10005 11681

Minimum Enclosing Ball / Minimum Bounding Sphere

三維空間的球，包圍所有點，體積暨表面積暨半徑最小。

Welzl's Algorithm。平均O(N)。

UVa 10095

Minimum k Enclosing Circle

二維平面的圓，包圍k個點，面積暨周長暨半徑最小。

Order k Voronoi Diagram。O(NlogN + k²N)。

二元搜尋半徑r。窮舉每個點，作為圓邊界，顯然圓心與該點相距r。旋轉的掃描線，圓繞該點一圈。O(logR ⋅ N ⋅ NlogN)。

承上，只取鄰點來掃描，以該點為中心，取正方形邊長4r之內所有點，確保點數低於k(16r²)/(πr²) < 5.1k。Range Tree。O(logR ⋅ N ⋅ (klogk + log²N))。

ICPC 7488

Maximum Empty Circle / Maximum Inscribed Circle

二維平面的圓，不含所有點和邊，面積暨周長暨半徑最大。

一群點最大空圓：圓心位於Voronoi Diagram的頂點上。如果平面有邊界，那麼圓心也可能在邊上。O(NlogN)。

凸多邊形最大內切圓：每條邊同時往垂直方向等速內縮。每條邊配合左右鄰邊的角平分線，就可求得消失所需距離。換個觀點，不內縮了，改為預測最快消失的邊，刪除此邊，左右鄰邊延長銜接於一點，就縮小問題範疇了。所有邊放入二元樹，按照消失順序排序，每當刪除一條邊就更新二元樹。O(NlogN)。

凸多邊形最大內切圓：二元搜尋內切圓半徑，以半平面交集驗證。O(NlogR)。

UVa 11257 ICPC 3890

簡單多邊形最大內接圓。【待補文字】

正交多邊形最大內接圓。【待補文字】

ICPC 2994

Minimum Enclosing Annulus

二維平面的環，內圍外圍圓心相同，包圍所有點。可令寬度最小、令面積最小。

建立Voronoi Diagram與Farthest Point Voronoi Diagram，窮舉三種情況。O(N²)。

一外三內：窮舉外點；窮舉圓心，即Voronoi Diagram的點。O(N²)。
兩外兩內：窮舉Voronoi Diagram的邊，
　　　　　窮舉Farthest Point Voronoi Diagram的邊，
　　　　　兩邊求交點，作為圓心。O(N²)。
三外一內：窮舉內點；窮舉圓心，即Farthest Point Voronoi Diagram的點。O(N²)。

Maximum Empty Annulus

Minimum Enclosing Triangle

二維平面的三角形，包圍所有點。可令面積最小、令周長最小。

Maximum Empty Triangle

二維平面的三角形，不含任何點，面積最大。

當平面沒有邊界，這個問題沒有討論意義；把三角形壓扁、拉長，即不含任何點、面積無限大。

如果設定了三角形的角度範圍，那麼就有討論意義了。

如果給定的平面擁有一個長方形邊界，然後多邊形是凸的呢？
這個時候就不會有面積無限大的多邊形了吧？

不是凸的形狀，就只能採用「頂點屬於給定的點集合」。
若是凸的形狀（如三角形、長方形、凸多邊形、圓形），
除了可以採用「頂點屬於給定的點集合」，
也可以採用「邊界碰到給定的點集合」。

這種時候就不知道如何命名了。

UVa 10112

Extremum Triangle

二維平面的三角形，一群點挑三點作為頂點。可令面積最小最大、令周長最小最大。

面積最小最大：點線對偶。O(N²)。

Minimum Enclosing Convex Polygon = Convex Hull

凸多邊形，包圍所有點，面積暨周長最小。

即「Convex Hull」。

Maximum Empty Convex Polygon
（Largest Empty Convex Subset）

凸多邊形，不含任何點，一群點挑幾個點作為頂點。可令頂點最多、令面積最大、令周長最大。

頂點最多：點線對偶，掃描線。O(N³)。

Minimum Enclosing Convex k-gon

凸k邊形，包圍所有點，可令面積最小、令周長最小。

Extremum Empty Convex k-gon
（Largest Empty Convex Subset）

凸k邊形，不含任何點，一群點挑k個點作為頂點，可判斷是否存在、令面積最小最大、令周長最小最大。

判斷是否存在：NP-hard。

面積周長最小最大：O(kN³)。

面積周長最大：O((kN + NlogN) ⋅ logN)。運用「SMAWK Algorithm」得加速到O(kN + NlogN)。

ICPC 2674

Extremum Convex k-gon

凸k邊形，一群點挑k個點作為頂點。可判斷是否存在、令面積最小最大、周長最小最大。

判斷是否存在，即「Erdős–Szekeres Conjecture」。

演算法同上。

Extremum Convex Hull of k Points

凸多邊形，邊界暨內部恰有k個點。可判斷是否存在、令面積最小最大、周長最小最大。

演算法同上。

Minimum Simple Polygon

簡單多邊形，所有點作為頂點，可令面積最小、令邊長最小。

NP-hard。

UVa 12386

Longest Segment in Simple Polygon

簡單多邊形，內部最長線段。

最長線段：必然碰到其中兩個頂點，否則可以旋轉線段變得更長。窮舉兩頂點，計算線段與多邊形交點。O(N³)。

最長對角線：O(N(logN)³)。

ICPC 4756

Maximum Convex Polygon in Simple Polygon
（Potato Peeling）

簡單多邊形，內部最大凸多邊形。把凹凹凸凸削平。

O(N⁷)。