用於接觸杆子的繩索的算法

Question

你有許多不同高度的杆子，均勻間隔開，還有一根繩子穿過它們的頂部。繩子拉緊，不下垂。顯然，繩子並不一定會碰到所有杆子的頂部 - 例如，如果杆子比杆子兩側的杆子短，那麼繩子就不會碰到杆子。

我們如何找到哪根杆接觸繩子，哪根不能？

我被告知有一種算法比n-squared快。

（未作業）

Answer 1

這基本上是convex hull problem。 （多邊形頂點是所有極點的頂部和第一個和最後一個極點的底部）。鏈接的Wikipedia頁面提供了幾個比O更好的算法（n ）。似乎最好的是marriage-before-conquest和Chan's algorithm，兩者都是O（n log h），其中n是極數（+2），h是繩子實際接觸的極數（也是+2）。

實際上，如果極點已經按x座標排序，則Graham scan和Monotone Chain算法是O（n）。