平面ポイントセット内のC凸孔の穴を見つける

Question

所定の点セットの凸孔を見つけるための効率的なアルゴリズムを探しています。 問題は

です

$ n $ euclidan平面内のポイント、定数 $ c $ を指定します。多くの空の凸型多角形 $ p_1、\ dots、p_k $ は、 $ i= 1、\ dotsの場合k $ ; $ p_i $ は、指定されたポイントセットから $ c $ 頂点を備えています。

おそらく凸の穴を見つけることを考慮した論文はいくつかありますが [1] [2] [3] 、そしてそのような穴の存在を示すもの [4] [5] 、私はそれらを見つけるためのアルゴリズムを説明する論文を見つけることができませんでした。

明らかに、 $ \ mathcal {}（n ^ c）$ に存在するナイーブアルゴリズムが気になる、各 $ c $ -subsetがトラバースされます。しかし、私はより効率的なアルゴリズムがあるかどうかを知りたいのですが。

Answer 1

「平面ポイントセットの凸状多角形のカウント」（ link ）Mitchell et al。time $ o（cn ^ 3）$ を実行できるアルゴリズムを表示します。

しかし、これらのポリゴンを報告する必要がある場合は、 $ O（n ^ c）$ よりも良くできません。="math-container"> $ \ omma（n ^ c）$ で始まるポリゴン（ $ n $ の凸形位置のポイントを考慮してください。）