空間が凸であるかどうかを確認するアルゴリズム

どのような？どの範囲を超えていますか？一次微分では不十分ですか？ –

何の多項式ですか？スペースを定義するポイントの数？ – AnnaR

私は彼がメートル法空間を意味していると思うので、どうやってデリバティブでそれを行いますか？ –

-2

うーん...興味深い質問です。私は答えがイエスだと信じています。おおまかに言えば、それぞれの面の平面方程式を見つけてください。結合された面の各対について、それらの間の角度が鈍角であれば、体積は凹である。これはO（log（n））時間で実行する必要があります。

私はグラフ彩色アルゴリズムを使用して、これをワークアウトのいくつかの方法があります賭けると思いますが、私はちょうどその巧妙ないんだけど...スペースの

2009-06-09 17:59:53

さて、これが受け入れられた後、下降声明はどうですか？ –

これはどのようにO（log（n））ですか？あなたは各飛行機のためにそれをやっています.. – Yogi

@ Yogi：何ですか？各面の平面方程式を求めることはO（1）である。結合された平面の対を比較するため、O（log（n））です。ポリゴンの平面方程式を求めるのは一定時間なので、O（1）なので、アルゴリズム全体の順序には影響しません。 –

もっと多くの単語を使用してください。

正確にあなたが求めていることを知ることはできません。私たちは推測するしかありません。

スペースが一般的に凸または凹であるとは思わない...音量または面積を意味するのでしょうか？いずれにしても、表面の複雑さが本質的に多項式になるとすれば、多項式時間を打ち負かすつもりだとは思わない。

2009-06-09 17:54:22 Karl

答えて