幾何アルゴリズム加速のための混合演算に関する研究

• 神田 毅

  (株)富士総合研究所科学技術グループ

• 杉原 厚吉

  東京大学大学院情報理工学系研究科数理情報学専攻

• 森本 康彦

  日本IBM(株)東京基礎研究所

書誌事項

タイトル別名

• Study on Hybrid Arithmetic for Acceleration of Geometric Algorithms
• キカ アルゴリズム カソク ノ タメ ノ コンゴウ エンザン ニ カンスル ケンキュウ

抄録

A widely used strategy to decrease the execution time of robust geometric algorithms using multiprecision integer arithmetic is the hybrid use of integer and floating-point arithmetic. In this strategy, multiprecision integer arithmetic is avoided if the sign decision in floating-point arithmetic used in advance is regarded as sufficiently reliable. It is important for this strategy to estimate the upper bound of the error calculated in floating-point arithmetic. However, the method of the estimation is not unique. The more tightly the error is estimated, the more frequently multiprecision integer arithmetic is avoided. However, a tight upper bound requires high computational cost. This paper investigates how the suitable estimation varies as the type and the scale of inputs vary. Experimental consideration is done using the incremental method for constructing the Voronoi diagram as an example of the geometric algorithm.

収録刊行物

• 日本応用数理学会論文誌

  日本応用数理学会論文誌 14 (2), 117-150, 2004

  一般社団法人 日本応用数理学会

詳細情報

• CRID: 1390001205767087488
• NII論文ID: 110001878250
• NII書誌ID: AN10367166
• ISSN: 09172246
• ISSN: 24240982
• DOI: 10.11540/jsiamt.14.2_117
• NDL書誌ID: 7011171
• Web Site: http://id.ndl.go.jp/bib/7011171
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7011171
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可