algorithm - ポリノムアークアルゴリズム?

Question

クラスで次の問題を見ましたが、解決策がわかりませんでした。この問題を解決するための手順をより詳細に説明したり、より良い解決策を教えてくれる人はいますか?:

平面上の n 個の点が与えられていると仮定します。頂点が指定された点で、辺が交差しない n-1 辺を持つ多角形の円弧を見つけます (隣接する辺は 180 度の角度を形成する場合があります)。操作の数は n log n のオーダーでなければなりません。

教師の解決策は次のとおりです。

x 座標に関してすべての点を並べ替えます。x座標が等しい場合、y座標を考慮して、すべての頂点を線分で（この順序で）接続します。

Answer 1

あなたの先生の解決策は（幸いなことに）良いです。これを視覚化してみます。

プロット上に点を描くだけです。次に、一番左の点から次の点まで線を引くことができます。このように、右に行くすべてのポイントを接続します。

すべての点の x 座標が異なる場合、それはうまくいき、線は交差しません。

同じ x 座標を持つポイントについては、最初に最低 (最小の y 座標) に移動し、次に上に移動します。そこにも交差点はありません。