Misc - IMAI Toshiyuki

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

今井 敏行

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

　View Summary

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

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

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

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

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

Report on ICIAM 99 Edinburgh Part 2(Conference Reports)

Tezuka Shu, Ushijima Takeo K., Imai Toshiyuki, Kubota Koichi

Bulletin of the Japan Society for Industrial and Applied Mathematics ( The Japan Society for Industrial and Applied Mathematics )  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  [Refereed]

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

Toshiyuki Imai （Part： Lead author )

Abstracts of the 9th Franco-Japanese Days on Combinatorics and Optimization     1996.10  [Refereed]

An Easy Method to Remove Degeneracies in Computational Geometry

IMAI Toshiyuki

IPSJ SIG Notes ( Information Processing Society of Japan (IPSJ) )  53 ( 96-AL-53 ) 103 - 110   1996.09

　View Summary

Geometric algorithms sometimes fail in the degenerate cases even without numerical errors. lt is difficult to make or imprement an algorithm which can treat any degenerate cases. To reduce the difficulty, some methods how to treat degeneracy systematically were proposed. In this paper, we present a method to treat degenerate inputs systematically in Geometric algorithms. It computes data which is required in degenerate case when executing the algorithm, while conventional methods adapt the algorithm as preprocess to treat the degeneracy. That's why it has no merit of execution time but it is easy to apply the already impremented program without changing the algorithm essentially.

What Is the Inverse of Minkowski Addition?

SUGIHARA Kokichi, IMAI Toshiyuki, HATAGUCHI Takeshi

Technical report of IEICE. PRMU ( The Institute of Electronics, Information and Communication Engineers )  96 ( 140 ) 33 - 40   1996.06

　View Summary

This paper proposes a new definition of the Minkowski addition for closed curves with certain properties. The conventional Minkowski addition call be considered as the binary operation for figures bounded by those closed curves. Conventionally, the inverse of this operation had been defined only for convex figures, whereas in the proposed definition the inverse can be defined naturally for all the closed curves.

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

A Combinatorial-Structure Oriented Algorithm for Voronoi Diagrams of Polygons

IMAI Toshiyuki

IPSJ SIG Notes ( Information Processing Society of Japan (IPSJ) )  45 ( 95-AL-45 ) 17 - 24   1995.05

　View Summary

An algorithm to construct Voronoi diagrams whose generators are points, line segments, chains and polygons is shown. This algorithm is adapted from a combinatorial-structure oriented algorithm for Voronoi diagrams of line segments. In this algorithm, Combinatorial structure of the diagrams is considered as prior information to numerical values. If the precision in computation is high enough for conventional algorithms to work well, this algorithm also constructs the correct Voronoi diagrams. Moreover, even when precision in computations is not enough, this algorithm ends up with a diagram as an output with several combinatorial properties which Voronoi diagrams must have. In this sense, this algorithm is robust against numerical error. This algorithm is designed in the assumption that numerical error exists ; hence it has not any exceptional rules for degeneracy but still works for degenerate cases.

A Combinatorial-Stracture Oriented Algorithm for Voronoi Diagrams of Polygons

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

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

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

A Failure - free Algorithm for Constructing Voronoi Diagrams of Line Segments

IMAI TOSHIYUKI, SUGIHARA KOKICHI

IPSJ Journal ( Information Processing Society of Japan (IPSJ) )  35 ( 10 ) 1966 - 1977   1994.10

　View Summary

Generalized Voronoi diagrams are not only theoretically interesting but also practically important. This paper presents a practical algorithm for constructing Voronoi diagrams of line segments. This algorithm is basically on incremental method but is modified by our new approach, called a topology-oriented approach, to a numerically robust algorithm. It is free from failure which otherwise comes from errors of computation. It always terminates normally with an output, and the output is guaranteed to have part of topological properties which the true solution should have. In ordinal levels of errors, the algorithm runs in O(n^2) time, which is no slower than conventional incremental methods. The time complexity is O(n^3) even in the worst case. The memory is O(n), which is theoretically optimal. Experiments on computers show that the practical performance of the algorithm was better than the above theoretical complexity.