1978年， M.I. Shamos's Ph.D. 的論文"Computational Geometry"標志著計算機科學的這一領(lǐng)域的誕生。當時他發(fā)表成果的是一個尋找凸多邊形直徑的一個非常簡單的算法， 即根據(jù)多邊形的一對點距離的最大值來確定。 

一、定義

旋轉(zhuǎn)卡殼算法在凸包算法的基礎(chǔ)上，通過枚舉凸包上某一條邊的同時維護其他需要的點，能夠在線性時間內(nèi)求解如凸包直徑、最小矩形覆蓋等和凸包性質(zhì)相關(guān)的問題。「旋轉(zhuǎn)卡殼」是很形象的說法，因為根據(jù)我們枚舉的邊，可以從每個維護的點畫出一條或平行或垂直的直線，為了確保對于當前枚舉的邊的最優(yōu)性，我們的任務就是使這些直線能將凸包正好卡住。而邊通常是按照向某一方向旋轉(zhuǎn)的順序來枚舉，所以整個過程就是在邊「旋轉(zhuǎn)」，邊「卡殼」。

二、應用

1. 計算距離

（1）凸多邊形直徑

（2）凸多邊形寬

（3）凸多邊形間最大距離

（4）凸多邊形間最小距離

2. 外接矩形

（1）最小面積外接矩形

（2）最小周長外接矩形

3. 三角剖分

（1）洋蔥三角剖分

（2）螺旋三角剖分

（3）四邊形剖分

4. 凸多邊形屬性

（1）合并凸包

（2）找共切線

（3）凸多邊形交

（4）臨界切線

（5）凸多邊形矢量和

5. 最薄截面

（1）最薄橫截帶

三、定理證明

1. 點集中最遠的兩個點一定出現(xiàn)在凸包的頂點上

證明：任取凸包內(nèi)部兩點，總能把連線延長至凸包邊界處得到更遠的兩點，之后對于邊界上的兩點又可以移動到頂點處得到更遠的兩點。也就是說在求最大距離時凸包內(nèi)部兩點會被頂點兩點覆蓋掉。

2. 凸包直徑 = 最大對踵點對距離 = 點集中兩頂點最大距離

左半部分證明：凸包直徑是距離最遠的兩條平行凸多邊形切線，對踵點對是卡住凸多邊形兩側(cè)切線的切點對。首先要知道在兩切線旋轉(zhuǎn)出最大距離時的對踵點對連線一定垂直兩平行切線，若不垂直則旋轉(zhuǎn)至垂直最優(yōu)，若旋轉(zhuǎn)至垂直后無法保證對踵點對不變則說明直徑變大了，這與前提矛盾。之后可知凸包直徑一定是某對對踵點對的距離，同時可以反證出其一定為最遠的那對對踵點。

右半部分證明：同樣用反證法，假設(shè)最遠對踵點對不是距離最遠的兩點，那說明還存在距離更大的兩點，垂直這兩點連線作凸多邊形兩切線可得到更遠的對踵點對，與前提矛盾。

3. 點集中構(gòu)成面積最大的三角形時三個頂點一定出現(xiàn)在凸包的頂點上

證明：若三角形三個頂點在凸包內(nèi)部則可以將頂點分別平移至凸包邊界上，此時得到面積更大的三角形，之后任取一邊為底邊，可以把剩余的一個頂點平移至該邊的切點位置，這樣可以進一步擴大三角形面積，對每條邊進行同樣處理可以發(fā)現(xiàn)最終三個頂點都位于凸包頂點處。也就是說任意的凸包內(nèi)部三角形都可以找到一個比它大的且頂點都在凸包頂點上的三角形來覆蓋，因此得出結(jié)論。

4. 點集中構(gòu)成面積最大的n邊形時其n個頂點一定出現(xiàn)在凸包的頂點上

證明：由于要求面積最大，那么這個n邊形一定是凸多邊形，不會是凹多邊形（凹多邊形求凸包會得到面積更大邊數(shù)更少的凸多邊形），在凸包內(nèi)部任取一個n邊形都能把n個頂點平移至凸包邊界上，之后類似上面那條結(jié)論的證明可以將n個頂點移動到凸包頂點位置來獲得更大的n邊形，得證。

5. 存在一對平行邊的四邊形其max(兩條對角線長) > max(兩斜邊長)

證明：這是比較顯然的，可以分兩種情況+勾股定理證明。

6. 最小矩形覆蓋一定有一條邊與凸包上一條邊重合

7. 凸包寬度 = 每條邊到最遠點距離的最小值

證明：首先要知道凸包寬度的定義，凸包寬度是任意兩條平行切線距離的最小值，另外還有一個結(jié)論，對于任意的“點-點”的兩條切線，總可以通過旋轉(zhuǎn)得到距離更小的“點-邊”切線或“邊-邊”切線。因此只需要枚舉每條邊，取所有邊到其最遠點距離的最小值。