極に触れるロープのアルゴリズム

Question

高さの異なる複数の極が均等に間隔を置いて配置され、ロープの上端を横切るロープがあります。ロープはきつく引き伸ばされ、垂れ下がることはありません。明らかに、ロープは必ずしもすべての極の頂点に触れるわけではありません。例えば、極が両側の2つよりも短い場合、ロープは決してその極に触れません。

ロープにどの極が触れているのか、どの極には触れていないのか

これは、n倍の高速アルゴリズムです。

（未宿題）

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）です。