為什麼常見的O(n)時間的找凸多邊形內最大內接三角形的那個演算法是錯誤的?

看到 chao xu的專欄 里提到一篇新出的 arxiv 論文 https://arxiv.org/abs/1705.11035 證明常見的O(n)時間的找凸多邊形內最大內接三角形的演算法是錯誤的,請問O(n)的演算法為什麼是錯誤的?

下面簡稱錯誤的演算法為 DC.

先說一下這個 DC 演算法被發現是錯誤的意義, 最大內接三角形是一個非常基礎而且是比較中心的計算幾何問題,這個錯誤的DC 演算法發表於1979年距今已經38年,之後很多研究者繼續研究這個方向的問題,像chao xu 提到的,求凸 n 邊形的最大內接 k 邊形的演算法,還有一些基礎演算法直接或者間接的又引用了 DC 的結論.而這些第二層的演算法結論往往又被其他這個方向更高層的計算幾何問題當做結論直接被引用.所以 DC 演算法是錯誤的會導致很多已經發出來的和它有關的這個領域的文章的結論不準確.所有這些文章的結論都要被重新審視!

另外一點,凸多邊形最大內接三角形這個問題收錄在 poj 上面,想必很多參加過演算法競賽的同學都見過這道題,也冥思苦想過這道題.我想很多來看這個回答的人,是因為這個原因!

反正答主當年看到 DC 演算法的時候,表情是這樣的,

內心是」哇,這樣也行」

而過了很多年,看到這篇文章的時候,表情是這樣的,

內心是這樣的」這..這樣也能錯!」 (圖片侵刪)

考慮到可能有非競賽黨,或者非計算幾何方向的人看這個答案,先簡要說一下 DC 演算法怎麼做.知道的同學可以直接看下一部分.

首先,這個問題,凸多邊形頂點的相鄰順序是已知的,這點很重要,否則要算這個相鄰順序,就需要 O(nlogn) 時間

1.選擇順時針方向或者逆時針方向為演算法運行的方向,然後整個演算法運行中,方向固定不變.

2.任選一個頂點 a, 叫做 root 點, 然後沿選擇的方向選取接下來的頂點 b,c.

3.沿著選擇的方向選 c 的下一個頂點替換 c, 如果替換後△abc 面積增大,那麼繼續替換 c, 直到如果更新 c,△abc 面積不會再增大

4.固定 a,c, 然後用 b 的下一個節點替換 b, 同樣不斷更新 b 直到△abc 面積不會增大.特別的如果 b 的下一個頂點是 c, 那麼停止更新 b.

DC 演算法稱停下來的這個三角形為a-anchored 三角形

5.記下這個三角形的面積,然後更新 a 成 a 之後的那個點,繼續重複3-5.有一個關鍵的地方是此時 b 不用重新設置為新的 a 的下一個頂點, c 也不用.這是保證 DC 演算法 O(n)時間的關鍵.不過 DC 演算法是錯的,我們這裡就不說當時 DC 為什麼覺得可以不用重置 b 和 c 了.

6.在每個點都計算出來的anchored三角形中找出面積最大的那一個

乍一看,這個演算法是不是很優雅?實現起來很簡單,而且先更新 c 再更新 b, 比較巧妙的利用了凸多邊形的性質和傳遞性,很容易看出,確實找到的三角形是從 a-c 路徑上所有頂點能夠成的內接三角形中最大的.

為了說明 VMJI 的做法,還有他們怎麼構造反例的,介紹一下2-stable 三角形的概念,(論文中對2-stable定義的其實不大清楚,乍一看,按照論文中2-stable 的定義,△a0a1a2不是2-stable 的,這裡我按照不影響論文的證明的前提下重新說一下我的理解)

依舊要先選定一個方向,如順時針,然後以△a0a1a2為例,如果我們可以先選定一個點a0稱作 root 點, root 點順時針方向先遇到 a1後遇到 a2,把 a0a1叫做supporting line. 如果△a0a1a2是以 a0a1作為一條邊,另一個頂點在 a1順時針到 a0的這段路徑上的頂點中面積最大的內接三角形,並且 △a0a1a2是以 a0a2為邊, 另一個頂點在 a0順時針到 a2的這段路徑上,面積最大的內接三角形,那麼我們稱△a0a1a2為2-stable 的.

2-stable 三角形和 anchored 三角形很像,按照 DC 的演算法,所有 anchored 三角形都是2-stable 的

DC證明演算法正確性的思路:

面積最大的內接三角形一定是」3-stable」 的

「3-stable」的三角形一定是」2-stable」 的

所以找到所有」2-stable」 的三角形,然後選擇他們當中最大的那一個,就是最大內接三角形

到上面為止都還沒有錯,但是

DC 認為以一個點為 root,只會有一個 2-stable三角形,所以他們演算法跑出來的被他們命名為 anchored 的2-stable三角形就是這個2-stable 三角形, 所以 DC 認為他們的演算法把2-stable 三角形找全了, DC 演算法正確性得證.但 VMJI 發現,對每個 root 點,不只會有一個2-stable 的三角形,而且第一個出現的2-stable 三角形不一定是面積最大的,DC 演算法並沒有找全2-stable 三角形.所以 DC 演算法可能不會跑到面積最大的那個三角形,從而錯了.

反例就是構造了三個2-stable 的三角形,而最大的內接三角形是△a0b0c0.不管以a0,b0,c0中哪個頂點為 root 點, 順時針方向跑演算法,DC 演算法都會先遇到一個2-stable 三角形,然後停止從而不會跑到△a0b0c0,從而失敗.

接著 VMJI 證明了任何兩個以同一個點a為 root 的2-stable 三角形△abc 和 △ab』c』,線段 bc 和 b』c』一定會相交,像反例中的c1c2和 a0b0相交,b0b2和 a0c0相交.而不會出現像下面這樣兩種相對位置的情況(證明過程用一點點幾何知識就行,這裡就不說了)

由此性質,我們很容易設計出一個 O(n)時間複雜度的演算法求出以 a 為 root 點的所有2-stable 三角形:像 DC 那樣求出第一個2-stable 三角形後,因為 bc 和 b"c"會相交,所以 bc兩個變數繼續往前遍歷,不需要考慮後退.直到遍歷完所有頂點.

要吐槽的一點是,VMJI 在證明」以同一個點a為 root 的2-stable 三角形△abc 和 △ab』c』,線段 bc 和 b』c』一定會相交」的過程中依舊不嚴謹,其實應該用到多邊形是凸的的性質,但是完全沒有提到.你們是想重蹈 DC 的覆轍么?

接著論文演示了一下,最壞情況下對任意一個 root 點,可以構造出 O(n)個2-stable 的三角形,像這樣微調一下頂點,每個同色三角形都可以是2-stable 的,而且這些三角形的面積沒有任何單調性:

給了個具體例子:

簡要說明一下論文後面提出的 O(n^2)和 O(nlogn) 的演算法,

O(n^2)的演算法,因為 O(n)時間就能找到所有以 a 為root 的2-stable三角形, 並且可以找到最大的那一個.對每個點都做為 root 算一次,取最大的,總複雜度O(n^2)

O(nlogn)的演算法,先任取一個點a作為 root,O(n)時間算出 以 a 為root 點的最大內接三角形,這個三角形會將凸多邊形分成三段,取最長的一段位置在正中間的那個原凸多邊形的頂點,記為 m. 以 m 為 root 再算一遍最大內接三角形.兩個三角形把凸多邊形分成6段,根據兩個三角形的相對位置不同可知最大內接三角形的頂點可以排除掉至少1/6n 個凸多邊形上的點,然後繼續重複做下去,用一下主定理分析複雜度,是O(nlogn)