Misc - IMAI Toshiyuki

Modular Methods to Determine the Sign of the Values of Polynomials and Their Applications to Computational Geometry

Imai Toshiyuki

IPSJ SIG Notes ( Information Processing Society of Japan (IPSJ) )  94 ( 35 ) 17 - 24   1994.05

　View Summary

Not a few geometric algorithms determine signs of values of polynomials whose variables are input data to decide the structure of geometric objects and require double or triple long integer arithmetics such as addition, subrtaction and multiplication even if all the input data are integers of single length. In the standard method, multiple long integer arithmetic takes much time, especially in multiplication. It has been known that modular arithmetic reduces time of such calculations. Modular arithmetic, however, has to use multiple long integer arithmetics to get back the values themselves from their residues and it takes the same or more time compared to the standard method. In this paper, we show some techniques to determine the sign of a double or triple long integer directly from the result of modular arithmetic method, and show the performances of the applications to a geometric problem of making a convex hull.

計算誤差に強い多角形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