我有一個凸多邊形P，我想將其分成三部分，如下所示：首先，線l1將P分成兩部分P1和P2，第二部分線l2將這兩個部分中的一個（例如P1）分成兩個部分P11和P12。我該如何做到這一點，以獲得三個部分P11，P12，P2的最大直徑最小的物體？或者我怎樣才能獲得近似結果？如何三區分凸多邊形使三部分的最大直徑最小化
首先，我想用三個圓來覆蓋多邊形，並儘量減少圓的最大直徑，但我也不知道如何獲得這樣的圓。我在這個問題上研究了很多，而且不能提出一個有效的算法。而且大部分研究都集中在如何劃分點。
是否有任何已知的算法來計算？非常感謝您的幫助！
蠻力就足夠了。
編寫一個將凸多項式作爲輸入的函數，依次嘗試所有對角線並將多邊形分爲兩部分。兩個部分的直徑很容易找到，既可以是分裂對角線的長度，也可以是初始多邊形的最長對角線的長度（如果該最長對角線屬於所考慮的部分）。
您將在兩個步驟中使用此功能，分割初始多邊形，然後分割第二部分。
作爲一種優化，您將保留迄今獲得的最短最大直徑的軌跡;當你嘗試一個新的分割時，嘗試一個比當前最小對角線長的第一個分割點沒有意義。
感謝您的回答。根據你的方法，多邊形將總是被對角線切割。但我認爲大多數時候，最佳切割可能是跨越兩個邊緣的線條，而不是恰好穿過頂點。考慮一個凸四邊形。首先，診斷把它分成兩個三角形，其次三角形不能用對角線分開。我誤解了你的想法嗎？ – Bruce 2014-11-25 02:59:33
是的，我低估了分裂可以跨越邊界的事實。那麼這個問題對我來說太難了。 – 2014-11-25 08:27:23
你的多邊形有多大？ （所以我們知道有多少蠻力是可行的） – arghbleargh 2014-11-24 03:50:04
有多大？你是指該區域或頂點？面積可能非常大，我們可以假設多邊形的頂點最多爲十個。蠻力是如何運作的？首先需要離散多邊形？ – Bruce 2014-11-24 05:27:17
「離散多邊形」是什麼意思？ – Codor 2014-11-24 07:37:55