情報システム評価学’９９レポート回答

問題１　〔やさしい問題）

自分で平面上に10個以上の点を打ち,　そのボロノイ図とドローネ三角形分割を書きなさい.

回答：

レポートを提出した22名全員が正しく (ちょっとしたケアレスミスはあったが）回答してくれました。 JAVAでAppletを書いてくれたのは木津　勇一郎さん。 Voronoi図作成。 こういう回答が理想的です。 Incrementalに、どんどん点を加えていけます。 重みつきバージョンまで書いてくれたのが 星さん、積極的でいい。 アルゴリズムの説明を つけてくれた人が2名(寺崎さん、岡さん）ともに非常に よく書けています。

問題２

ソーティングの2次元への拡張のアイデア(講義で紹介されていないもの）を考えなさい

回答：

　 これは星の数ほどあります.　 データに順番をつける、あるいはデータの近さを測る構造を 作るといったことに対応するものならなんでもいい。 階層的ボロノイ図と呼ばれるものに近い構造、 4分木、グラフの最短路、最大フロー〔もう少し説明がほしいが） などが回答にあった。 私が思いつくのは,　可視問題〔観測者の視点からみえる図の 観測点による変化を記述するデータ構造を作る問題)、 障害物のある配置でのロボットの移動可能領域と 移動路を記述する構造、 クラスタリング〔例えば,K個の円で 点集合を被覆する問題）、 地震などの波の到達時刻を高速に判定するデータ構造　 など。

問題３　〔やさしい問題）

2次元の凸多角形Pの頂点が点集合として与えられたとき,　任意の直線に対し、　直線がPと交差するかどうかの判定をO(log n) で行ないたい。　どのようにデータ構造を持っておけばよいか、どのように判定するかを答えなさい。　 ただし、ｎ　はPの頂点の数.　

　回答：

　 これは講義でやった接線を求める問題とほとんどおなじ. 特に回答はあたえない。

問題４

　次の問題の解法の欠点もしくは誤りを指摘しなさい
　　 問題：　ｎ頂点の凸多角形　P　がある。　(n>4)　このとき,Pを含む最小面積の4角形を求めよ
解法：　P　の　ｎ本の辺から4本を取り出すすべての組み合わせを考える。これらの組み合わせから出来る4角形をすべて調べ,　面積最小のものを出力する

問題５　〔難しい問題）

上の問題４に対する良い解法を考えなさい　

回答：

　 この問題はグラフィクスでは基本的な問題の一つ（の易しいバージョン） ですが、この解法では正しい答えが出ません.　 これを指摘したのは4人。 解の効率が悪いという点の指摘は3人。これも事実だが 二次的な問題。小松さんは両方指摘,　説明も一番詳しい。
例えば正5角形を考えます.　４辺を選んで４角形を作ると、 細い角が出来てしまいますね.　これよりも、隣り合った３辺 を選んで.　もう一つの辺は残った頂点に接する〔中点で接する） ように作った４角形のほうが面積が小さいです。　

実社会でのシステム設計でもこういう事があります. プロジェクトのリーダー的な人がアルゴリズム設計でこういう間違いを すると非常にやばい。
で、解法の修正は少し難しく、誰も手をつけていません. 次のような定理があります.

定理。　凸ｎ角形Ｐに外接する最小面積のｋ角形として、 Ｐのｋ本の辺の延長からなるか,あるいは Ｐのｋ-１本の辺の延長と、Ｐの一つの頂点ｖで接する線分e からなるものが存在する.　後者の場合,　ｖはeの中点で接する

この定理はＤｅＰａｎｏという人の論文にあるのですが、 出版されていない。 の証明は私も試みたことがありますが, 解析的で結構ややこしいです。 これを用いるとｋ=４なら、３本の辺と、一つの頂点を決めると 全部試せば問題は解けます.　でも非常に 効率が悪いし、ｋが大きくなると手に負えない。 ダイナミックプログラミングを用いると、 ｋが大きくても$O(n^3 \log k)$で出来ます〔考えてみてください）。 最速の方法は文献１の$O(n^2 \log n \log k)$ですが、もっと速い方法が あるかもしれません. なお、Ｐのｋ個の辺からなる多角形で面積最小のものは もっと高速に計算できます〔文献２）。
文献 1 : A. Aggarwal, J.S. Chang, C. K. Yap, Minimum area circumscribing polygons, The Visual Computer 1 (1985), pp.112-117
文献２：A. Aggarwal, B. Schieber, T. Tokuyama, Finding a minimum weight k-link path in graphs with the concave Monge property and applications, Discrete and Computational Geometry 12 (1994), pp.263-280. 　　

問題６

次の問題の解法の欠点もしくは誤りを指摘しなさい。
問題：　重心を中心に1秒間に1回転しながら速度vで(重心が）直線的に進む平面上の凸ｎ角形Pがある。データ構造を用意して、重心の位置とPの現在の回転角度、更に進む方向が与えられたとき、何秒後に半平面$y <　0$と衝突するかを出来るだけ速く判定したい.
解法：　任意の直線との交差判定がO( log n ) で判る構造〔問題３参照）を用意する.　適当な時刻ｔを取り,　このとき,重心のｙ座標が０未満か、又は凸包と直線$y=0$が交差しているならば、時刻ｔではすでに衝突している。一方、そうでなければ,　現在衝突していない。
これを用いてｔについて二分探索をおこなう。すなわち,　衝突していない場合は時刻を2ｔにし、衝突している場合はt/2にする。　一般に、それまでに見出した衝突している最小時刻ｔと衝突していない最大時刻ｔ’があったとき,　時刻　（ｔ＋ｔ’）/2での衝突の判定をする操作を続ける.　これにより,　衝突時刻を計算する。

回答：

これに対する回答は一件、佐々木さんのみ. ちょっと記述がややこしかったかもしれませんが、この解法の バグはもっと深刻です.

この解法である時刻ｔでPと半平面が交差していないとしましょう. するとアルゴリズムは最初の衝突時間はｔより後だと判定して 時刻２ｔでの衝突判定を行います.　結果として, 最初の衝突時間としてはｔより後の時刻を報告します.
でも、ｔで交差していなくても　ｔより前の時刻で既に 衝突している可能性があるのです。 Pとして、ヘリコプターのプロペラを考えてください. プロペラが半平面（を決める水平線）と平行だと、 プロペラの中心が水平線にぶつかっていない限り交差はしません. でも、その前にプロペラが垂直位置に近いときにぶつかっていますよね.
ですから、この解法は駄目です。　衝突回避を自動的に行う ナビゲーションシステムで、高速性を追求するあまり、 こんなアルゴリズムを組んだら大変な惨事になります。

　問題７(難しい問題)　　　　　　　

　衝突時間に0.5秒の誤差を許していいときに、 上の問題に対する良い解法を考えなさい。

回答：　

ちょっと面倒なので,　詳しい回答は省略。　 ０.２５秒の間の軌跡は４分円と直線で囲まれた図形になります. これを使いましょう。

　問題８

　２−３木の基本操作　 〔Search,　Insert, Delete) をレポート用紙5枚以内にまとめなさい 〔参考書を見てもよい）.　出来れば,　 Merge　Splitも書けばBetter　〔この場合は枚数を追加しても良い〕。

　回答　

これは皆さんよく出来ていました.　感心しました。

　問題９

　3次元の凸包を計算するアルゴリズムを考えて、計算時間を評価してみてください。

　回答：

きちんとしたアルゴリズムを書いてくれたのは星さん。 分割統治法で、非常によく書いてあります. ９ページもあるので,ちょっとここには紹介できません. 一般的な回答なら授業中紹介した教科書等を見てください.

　問題１０　

　自分が興味を持っているコンピュータ科学の問題に付いて 徳山にわかるように説明してください。

　 回答：

皆さんしっかりした意見や興味を持っていて,非常に 参考になりました.　ありがとう。

面倒なので全員には返却はしません。 返却してほしい人は連絡してください.