講演抄録/キーワード |
講演名 |
2008-03-10 14:25
Consistent Digital Rays Jinhee Chun・Matias Korman(Tohoku Univ.)・Martin Noellenburg(Karlsruhe Univ.)・○Takeshi Tokuyama(Tohoku Univ.) COMP2007-61 |
抄録 |
(和) |
$d$-次元グリッド上の中心点$o$から各グリッド点$p$へ向かうデジタル直線$\dig(op)$の集合の数学的に整合的な定義を与える.
各デジタル直線は$\dig(op)$は点$o$と点$p$の間のユークリッド線分$\seg{op}$を近似し、すべてのデジタル直線の集合がユークリッド公理に類似した公理系を満たす.
デジタル直線と対応するユークリッド線分の間の近似誤差は最大ハウスドルフ距離で評価し、$n\times n$グリッド平面内での誤差に対し、漸近的に最適な$\Theta(\log n)$の誤差限界を与える.
誤差限界の証明はディスクレパンシー理論とシンプルな構築アルゴリズムに基づいている.
さらに、デジタル直線の単調性がなければ、誤差限界は$O(1)$に抑えられることを示す. |
(英) |
Given a fixed origin $o$ in the $d$-dimensional grid, we give a novel definition of {\em digital rays} $\dig(op)$ from $o$ to each grid point $p$. Each digital ray $\dig(op)$ approximates the Euclidean line segment $\seg{op}$ between $o$ and $p$. The set of all digital rays satisfies a set of axioms analogous to the Euclidean axioms. We measure the approximation quality by the maximum Hausdorff distance between a digital ray and its Euclidean counterpart and establish an asymptotically tight $\Theta(\log n)$ bound in the $n\times n$ grid. The proof of the bound is based on discrepancy theory and a simple construction algorithm. Without a monotonicity property for digital rays the bound is improved to $O(1)$. |
キーワード |
(和) |
デジタル直線 / 近似アルゴリズム / ディスクレパンシー / 計算幾何学 / / / / |
(英) |
Digital Ray / Approximation Algorithm / Discrepancy / Computational Geometry / / / / |
文献情報 |
信学技報, vol. 107, no. 537, COMP2007-61, pp. 39-46, 2008年3月. |
資料番号 |
COMP2007-61 |
発行日 |
2008-03-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-61 |