rectangle

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²)。

circle

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

triangle

minimum enclosing triangle

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

maximum empty triangle

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

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

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

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

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

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

UVa 10112

extremum triangle

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

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

convex polygon

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個點。可判斷是否存在、令面積最小最大、周長最小最大。

演算法同上。

polygon

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⁷)。