Misc - 今井　敏行

剰余計算の並列化による誤差なし図形処理とその実装

今井 敏行

情報処理学会研究報告. AL, アルゴリズム研究会報告 ( 一般社団法人情報処理学会 )  89 ( 32 ) 41 - 48   2003年03月

　概要を見る

計算機上での図形処理を厳密に行なうためには,比較的簡単な場合でも,入力データが1倍長の整数なら数倍長から数十倍長の誤差なし整数計算が必要である.入力が倍精度浮動小数点数で,誤差無しの計算を整数で行なうと数百倍長の整数計算が必要である.このとき,特に乗算に計算時間がかかる.本稿では,計算時間の増大を抑えるため剰余計算を用い,多倍長整数を復元することなく正負の符号判定を行なう方法を提案する.さらに,剰余を取る法ごとに計算を並列化させ,PCクラスタ上で実装する.また小規模な例について数値実験を行なった結果により,通信速度が問題であることを示す.

幾何アルゴリズムの退化対処の剰余計算による実現

日本応用数理学会2003年度年会講演予稿集   340-341   2003年

漢字テキストアートの字形を利用した高精細化

日本応用数理学会2003年度年会講演予稿集   342-343   2003年

ICIAM 99 Edinburgh報告 その2(学術会合報告)

手塚 集, 牛島 健夫, 今井 敏行, 久保田 光一

応用数理 ( 一般社団法人 日本応用数理学会 )  10 ( 1 ) 66 - 69   2000年

DOI

Symbolic perturbation based on Gr(]E88D8[)bner basis

Abstracts of the 4th ICIAM     104   1999年

一般化Voronoi図の領域面積の計算法

日本応用数理学会1999年度講演予稿集     170 - 171   1999年

幾何的アルゴリズムの簡易な退化対処法とその実装

日本応用数理学会1998年度年会講演予稿集     130 - 131   1998年

A simple method to treet degeneracies in geometric programs

Abst. 14th European Warkshop on Comp. Geom.     103 - 105   1998年

An Algebra for Slope-Monotone Closed Curves.

Kokichi Sugihara, Toshiyuki Imai, Takeshi Hataguchi

Int. J. Shape Model.   3 ( 3-4 ) 167   1997年  [査読有り]

DOI

幾何的アルゴリズムへの剰余計算の利用法

日本応用数理学会1997年度年会講演予稿集     304 - 305   1997年

Some methods to determine the sign of a long integer from its remainders.

Toshiyuki Imai

Proc. 9th Canadian Conf. in Comp. Geom.     117 - 122   1997年

How to get the sign of integers from their residuals

今井敏行 (担当区分： 筆頭著者 )

Abstracts of the 9th Franco-Japanese Days on Combinatorics and Optimization     1996年10月  [査読有り]

幾何的アルゴリズムの簡易な退化解除法

今井 敏行

情報処理学会研究報告. AL, アルゴリズム研究会報告 ( 一般社団法人情報処理学会 )  53 ( 96-AL-53 ) 103 - 110   1996年09月

　概要を見る

幾何的アルゴリズムは誤差がないものとしても退化時に破綻する. すべての退化に対処することはアルゴリズムの考案や実装を困難にする. この困難に対して, 既存のアルゴリズムでの退化の統一的な扱い方が研究されてきた. 本論文では, 幾何的アルゴリズム中で退化入力を統一的な扱う方法を提案する. 従来の方法があらかじめアルゴリズムを調べ, 退化に備えてアルゴリズムを書き改めておくのに対して, 本論文で提案する方法は, 退化時に必要なデータをアルゴリズム実行時に計算していく. そのため, 計算速度で利点はないが, 実装プログラムに対して基本的に変更がいらず, 簡単に適用できるという利点がある.

図形のミンコフスキー和の逆演算は何か

杉原 厚吉, 今井 敏行, 畑口 剛之

電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解 ( 一般社団法人電子情報通信学会 )  96 ( 140 ) 33 - 40   1996年06月

　概要を見る

図形のミンコフスキー和を,ある条件を満たす閉曲線同士の演算として定義しなおすことを提案する.従来のミンコフスキー和は,この閉曲線で囲まれた領域同士の演算であると解釈できる.また,この演算の逆演算はいままでは凸な図形に対してのみ定義されていたのに対して,ここで提案する新しい定義に基づけば,凸とは限らないより一般の図形に対して逆波算が素直に定義できる.

A Topology Oriented Algorithm for the Voronoi Diagram of Polygons.

Toshiyuki Imai

Proc. 8th Canadian Conf. in Computational Geometry ( Carleton University Press )    107 - 112   1996年

新しいミンコフスキー和の提案(共著)

日本応用数理学会平成8年度年会予稿集     278 - 279   1996年

組合せ構造を優先した多角形 Voronoi 図の構成法

今井 敏行

情報処理学会研究報告. AL, アルゴリズム研究会報告 ( 一般社団法人情報処理学会 )  45 ( 95-AL-45 ) 17 - 24   1995年05月

　概要を見る

点,線分,折れ線,多角形を生成元とするVoronoi図を構成する算法を示す.位相優先法に基づく線分Voronoi図の構成算法を拡張することによって実現した.図形のもつ組合せ構造を優先的に扱っている.一般の算法で正常な出力が得られる程度の計算精度の下では,この算法でも正常な出力を同等の計算量と記憶量で得ることができる.また,どのような計算精度の下でも正常終了し,出力が本来もつ組合せ構造のいくつかを保証する.この意味で本算法は計算誤差に対して強い.また誤差を前提にする算法であるため,入力が退化している状況でも算法は正常に働き,退化のための例外処理が不要である.

A Combinatorial-Stracture Oriented Algorithm for Voronoi Diagrams of Polygons

IPSJ SIG nots   ( 95-AL-45 ) 17 - 24   1995年

記号摂動法と剰余演算による符号判定法の応用

日本応用数理学会平成7年度講演予稿集     204 - 205   1995年

誤差による破綻の心配のない線分Voronoi図構成算法

今井 敏行, 杉原 厚吉

情報処理学会論文誌 ( 一般社団法人情報処理学会 )  35 ( 10 ) 1966 - 1977   1994年10月

　概要を見る

平面上の点の勢力圏を表す図であるVoronoi図を一般化することは、理諭的に興昧深いだけでなく、実用上も重要である。本論文では、線分Voronoi図の実用的な構成寡法を考案する。この新しい算法は、従来の逐次添加型の算法に、位相優先法と我々が呼んでいる数値誤差対策を適用したものである。この算法は、計算誤差による破綻を完全に防止でき、必ず結果が出力される、さらに、出力が本来持つはずの位相的な性質のいくつかが保証される。単精度浮動小数点程度の誤差が発生する環境では、線分数nに対して、理論的に従来並みのO(n2)の速度を確保することができ、最悪の場合でもO(n3)時間で処理を終了する。記億量はO（n）であり、理論的に最良である。また、算法を計算機上に実装し、実際こは、さらに高速に計算できることも計算機実験で確かめた。