2回生のkiritaです。コンピュータ・ジオメトリの勉強会を行いました。
この勉強会は過去すでに2回行っていて今回が3回目となります。大体の目安としては1回に1章、部員のやりたいところをやる、という進み方で、今回は第5章の幾何データ構造についてでした。
この章では、直交領域探索*1という1つの問題に対して、まずは1次元から出発し多次元に対応したり計算量をどんどん改善していったり…ということをします。具体的には、kd木、領域木、フラクショナルカスケーディングなどが登場しました。
結構むつかしい内容で、僕は発表をするためにスライドを作ったのですがかなり時間を食ってしまって、最後のほうは泣きながらOpenOfficeをポチポチしてました。その甲斐あってかどうか、台風ソングダが近づくなか参加者も少なかったのですが、わりと評判もよく聞いていた人も理解してもらえたようです。
次回は第6章の点位置決定問題について、発表はeha君です。がんばれ〜
*1:平面や空間に点がたくさんあるときに、ある直交領域に含まれる点を列挙するというクエリをどんどんさばく
