Misc - 今井　敏行

剰余演算による多項式の符号判定と計算幾何学への応用

今井 敏行

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

　概要を見る

計算幾何学のアルゴリズムには入力が単長整数でも,計算機内で入力変数の多項式の値の符号を判定する必要が生じ,加減乗算の結果,桁数が2倍長や3倍長程度に達するものが少なくない.一般に多倍長整数の符号判定のために多倍長演算を用意すると各演算に時間がかかる.剰余演算を利用して演算時間を短縮する方法が知られているが,剰余から数値を復元するために,結局多倍長演算と変わらないことになる.本稿では,2,3倍長程度の整数に対し,剰余演算の結果から直接に符号判定を行なう方法を提案する.さらに,その方法と普通の多倍長演算による方法をシミュレートした凸包構成プログラムで計算時間を比較した結果を報告する.

計算誤差に強い多角形Voronoi図の構成法

日本応用数理学会 平成6年度年会講演予稿集     40 - 41   1994年

Finger Treeを利用したマージソートの計算時間実測(共著)

日本応用数理学会 平成5年度年会講演予稿集     243 - 244   1993年

計算誤差に強い線分Voronoi図の構成法

応用数理学会平成4年度年会研究発表予稿集   243-244   1992年

An algorithm to construct line segment Voronoi diagram robust against numerical errors

Proc. Annu. National Conf. JSIAM   243-244   1992年

Topology-oriented approach to robustness and its applications to several Voronoi-diagram algorithms (共著)

Proceedings of the Second Canadian Conference in Computational Geometry     36 - 39   1990年

A Combinatorial-Structure Oriented Algorithm for Voronoi Diagrams of Line Segments

IPSJ SIG Notes   89 ( 89 )   1989年

組合せ構造を優先した線分ボロノイ図の構成法

情報処理学会研究報告89-AL-11   89 ( 89 )   1989年