| 講演名 | 2002/11/22 精度保証された反復反射計算の実装法 永井 孝幸, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では,単純多角形領域内のある一点から発した光線が領域の辺で繰り返し反射しながら進んでいくときの軌跡を計算するという問題(反復反射計算)を考える.累積誤差によって反射する辺の判定に誤りが生じると一般にはその後の軌跡が真の軌跡と大きく異なってしまうことから,単純に浮動小数点演算を用いて計算された軌跡は信用することができない.そこで,幾何アルゴリズムの実装に利用されている厳密計算ライブラリを用いることで反射辺の判定を正確に行い,軌跡の精度保証を行うことを考える.厳密計算では計算のオーバーヘッドが常に問題になる.今回扱う問題では反射回数が増すにつれて途中計算に要する計算ビット長が増加することから,単純な実装ではごく少ない回数の反射しか計算できない.計算に要するビット長の観点から算法を見直し,反射計算を行う多角形領域の辺の傾きに制限を加えることで軌跡の厳密計算に必要なビット長を反射回数に比例する程度に抑えられることを示す. |
| 抄録(英) | We consider the problem of computing the trajectory of iterative reflections of a ray emanating from a point in a polygonal region. A simple implementation of this computation with floating point arithmetic does not give a meaningful result because accumulated errors incur a misjudgement on which edge the ray will hit next, that results in a quite different trajectory. To compute an accuracy guaranteed trajectory, we implement this computation with exact geometric computation library. In exact geometric computaiton, we must care the bit-complexity of a computation because the time needed in a primitive arithmetic operation is not a constant but a function of the bit length of its operands. A straightforward implementation of iterated computation of reflection with the library shows a very poor performance because of its high bit-complexity arising from cascaded geometric computation. From the view of bit-complexity, we refine the computation and show that if we restrict the angles of the edges of polygon, we can implement the computation with exact geometric computation library within a bit-complexity proportional to the number of reflections. |
| キーワード(和) | 厳密計算ライブラリ / 精度保証 / 反射計算 |
| キーワード(英) | computational geometry / exact computation / cascaded computation |
| 資料番号 | COMP2002-46 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 精度保証された反復反射計算の実装法 |
| サブタイトル（和） | |
| タイトル（英） | Accuracy guaranteed computation of iterative reflections with exact geometric computation library |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 厳密計算ライブラリ / computational geometry |
| キーワード(2)（和/英） | 精度保証 / exact computation |
| キーワード(3)（和/英） | 反射計算 / cascaded computation |
| 第 1 著者 氏名（和/英） | 永井 孝幸 / Takayuki NAGAI |
| 第 1 著者 所属（和/英） | 鳥取環境大学 環境情報学部 Tottori University of Environmental Studies |
| 発表年月日 | 2002/11/22 |
| 資料番号 | COMP2002-46 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 490 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |