練習計算幾何：半邊緣，下一個和雙胞胎

Question

我正在努力解決練習本書「計算幾何 - 算法和應用，德貝格」。練習[2.7]說：「給定雙（e）= Next（e）對每個半邊e有效的細分的雙連接邊列表表示，該細分最多可以有多少個面？

我認爲解決方案是隻連接兩個頂點的邊，而雙胞胎可能是下一個。所以，唯一的臉可能是無限的臉。它們可以是更多的由邊緣鏈接的頂點對，但僅當它們彼此不相交時。有其他的可能嗎？

Answer 1

我會說你是對的。 IncidentFace（Next（e））等於IncidentFace（Twin（e）），因爲Next（e）對於所有半邊e均等於Twin（e）。由於我們知道IncidentFace（e）總是等於IncidentFace（Next（e）），因此我們可以得出結論IncidentFace（e）等於所有半邊的IncidentFace（Twin（e））。所以沒有邊緣位於兩個不同面孔的邊界上。如果沒有邊界限定兩個不同的面，那麼不能有多於一個面。