反對數的上限是多少？

對映體對是一對頂點的x，y，使得我們可以得出平行切線凸包通過頂點的x和y 1h而不需相交H.反對數的上限是多少？

我發現很多算法來找到這樣對，但我不能夠推導出可能配對數的上限。

有人可以給n個數的凸包的上界並證明它嗎？

2014-09-25 CodeLover

參見Preparata＆Shamos的計算幾何，定理4.18。當您圍繞多邊形旋轉切線時，它會依次觸碰每個頂點（N次移動）;同時，反對頂點也在輪廓上前進（N個移動，沒有回溯）。當沒有邊平行時，有N對。對於平行邊緣（最多N/2對），反對數不超過3N/2。 – 2014-09-25 21:19:01

查看計算幾何by Preparata & Shamos，定理4.18。當您旋轉多邊形周圍的切線時，它會依次觸及每個頂點（N移動）;當您旋轉多邊形周圍的切線時，它會依次觸及每個頂點（N移動）。同時，對角頂點也在輪廓上前進（N移動，沒有回溯）。

當沒有平行邊緣時，確切地有N對（一邊沒有移動與另一邊移動一致）。當有平行邊緣時，可能會有額外的一對，總數爲N + P，其中P是平行邊緣對的數量，最多爲N/2。

2014-09-25 21:20:57

我無法找到該書。你能否提一下這樣的證明，這將是非常有用的。謝謝 – CodeLover 2014-09-26 04:11:21

不，文字太長了。但原則是顯而易見的。 – 2014-09-26 07:31:13

請上傳圖片或文字，你不需要輸入。 – CodeLover 2014-09-26 08:05:45

回答