Misc - IMAI Toshiyuki

トランプのシャッフル方法の組み合わせにおける無作為性の評価

西川和希, 今井敏行, 床井浩平

映像表現・芸術科学フォーラム 2020講演予稿集     2020.03

図​形​処​理​に​お​け​る​近​似​算​法​に​よ​る​構​造​厳​密​性​の​保​証

今井敏行 （Part： Lead author )

日本応用数理学会2019年度年会講演予稿集     2019.09

確率的表現に基づく消失点の安定検出に関する研究

舛本高紀, 陳謙, 今井敏行

情報処理学会 第81回全国大会講演予稿集     2019.03

Bezier曲線を生成元とするVoronoi図の位相構造の決定

辻野弘章, 今井敏行

情報処理学会 第81回全国大会講演予稿集     2019.03

直線の確率表現に基づく消失点の安定検出に関する研究

舛本高紀, 陳謙, 今井敏行

2018年度 情報処理学会関⻄支部 支部大会講演予稿集     2018.09

構造情報処理の厳密性を保証する近似図形処理フレームワーク

今井敏行 （Part： Lead author )

    2018.09

消失点検出のための直線の確率表現に基づく投票法

舛本高紀, 陳謙, 今井敏行

日本応用数理学会2018年度年会講演予稿集     2018.09

Bezier曲線を生成元とするVoronoi図の厳密な位相構造の決定

辻野弘章, 今井 敏行

2018年度 情報処理学会関⻄支部 支部大会講演予稿集     2018.09

Bezier曲線を生成元としたVoronoi図の正確な隣接関係の決定

辻野弘章, 今井 敏行

日本応用数理学会2018年度年会講演予稿集     2018.09

２次元Delaunay図の逐次添加型３次元構成と入力順序によるパフォーマンス

岩本龍馬, 今井敏行

日本応用数理学会研究部会連合発表会     2018.03

Bezier曲線を生成元とするVoronoi図の正確な位相構造の決定

辻野弘章, 今井敏行

応用数理 学生・若手研究者のための研究交流会     2018.03

生成元として円と線分が混在したVoronoi図の位相的に厳密な近似構成

今井敏行 （Part： Lead author )

日本応用数理学会2017年度年会講演予稿集     2017.09

2次元Delaunay図の逐次添加型3次元構成と入力順序による速度比較

岩本龍馬, 今井敏行

日本応用数理学会2017年度年会講演予稿集     2017.09

点列近似によるBezier曲線のVoronoi図の位相的に正確な構成

辻野弘章, 今井敏行

日本応用数理学会2017年度年会講演予稿集     2017.09

領域隣接情報が厳密な円のVoronoi図の近似構成の性能評価

今井 敏行

第79回全国大会講演論文集   2017 ( 1 ) 187 - 188   2017.03

　View Summary

円のVoronoi図は点のVoronoi図とは異なる性質をもち，構成法を新規に開発する必要がある．円周を一様に点列近似し点のVoronoi図の構成法を利用する近似構成法も，よく用いられるが，精度と計算量が両立しない．厳密な位相情報の獲得のみ注力して，一様な近似をやめ，近似点数を減らすことで高速化けした構成法を提案した．本研究では，この構成法について，円を近似した点の総数の観点からこの構成法の計算量の評価実験を行い，この構成法の高速性を示す．

Delaunay図とLp-Delaunay図のメッシュとしての複数規準による形状比較

岩本 龍馬, 今井 敏行

第79回全国大会講演論文集   2017 ( 1 ) 237 - 238   2017.03

　View Summary

凸多角形内に点集合があるとき，凸多角形の内部を単体で分割したものを三角形分割と呼ぶ。Delaunay図とは、2次元において、最大角最小や最大外接円最小といった性質をもつ三角形分割である。有限要素法において、メッシュに用いられる三角形はつぶれていないものが望ましいため、上記の最適性を持つDelaunay図が自動分割によく用いられる。Delaunay図は2次元では最適性が証明されているが、3次元ではつぶれた四面体が発生することが知られている。また、Delaunay図はその最適性の証明があるために、十分に調べられていない。本研究では、2次元において点同士の接続関係の条件を変化させたLp-Delaunay図を用いて、形状変化の比較実験を行った。Lp-Delaunay図はp=2のときDelaunay図になる一般化である。

Simple Construction of Delaunay Diagram through 3D Convex Hull and an Improvement of its Time Performance

岩本 龍馬, 今井 敏行

情報処理学会関西支部支部大会講演論文集 ( [情報処理学会関西支部] )  ( 2017 ) 3p   2017

A Simplified Rapid Search Restricted to Voronoi Diagrams

辻野 弘章, 今井 敏行

情報処理学会関西支部支部大会講演論文集 ( [情報処理学会関西支部] )    3p   2017

Lp-Delaunay図のp=2の周辺におけるメッシュ形状最適性の実験的多面評価

岩本龍馬, 今井敏行

日本応用数理学会2016年度年会講演予稿集     2016.09

位相的に厳密な円や線分のVoronoi図の統一的近似構成

今井敏行 （Part： Lead author )

日本応用数理学会2016年度年会講演予稿集     2016.09

Experimental evaluations of the shape optimality of the Delaunay diagram in Lp Delaunay diagrams

岩本 龍馬, 今井 敏行

情報処理学会関西支部支部大会講演論文集 ( [情報処理学会関西支部] )  ( 2016 ) 3p   2016

近似的手法による線分L∞ボロノイ図の構造的に厳密な構成

友永優音, 今井敏行

日本応用数理学会2015年度年会講演予稿集     2015.09

円の勢力圏分割の点列近似による構造的に厳密な構成

樋口雄大, 今井敏行

日本応用数理学会2015年度年会講演予稿集     2015.09

白地図内の県名等最大化に向けたL∞ボロノイ図の構成

友永優音, 今井敏行

日本応用数理学会2014年度年会講演予稿集     2014.09

Delaunay図構成における退化への完全対処と簡易部分対処

今井敏行 （Part： Lead author )

日本応用数理学会2014年度年会講演予稿集     2014.09

計測曲線の美的意図に基づく数理的修正

今井敏行

日本応用数理学会2013年度年会講演予稿集     2013.09

Delaunay図構成への汎用退化対処法の適用

今井敏行

日本応用数理学会2013年度年会講演予稿集     2013.09

オペレーターオーバーローディングを利用した記号摂動による幾何プログラムの入力退化への汎用的自動対処の実現

山本修作, 今井敏行

日本応用数理学会2013年度年会講演予稿集     2013.09

図形プログラムの入力退化とその対処

今井敏行 （Part： Lead author )

日本応用数理学会2012年度年会講演予稿集     2013.08

デザイナーの意図を考慮した描かれた曲線の数理的修正

今井敏行 （Part： Lead author )

日本応用数理学会2012年度年会講演予稿集     2012.08

図形処理における入力退化の程度と簡易対処法

今井敏行 （Part： Lead author )

日本応用数理学会2011年度年会講演予稿集     2011.09

測定された曲線のデザイナーの美的意図に基づく数理的修正

今井敏行 （Part： Lead author )

日本応用数理学会2010年度年会講演予稿集     2010.09

多角形Voronoi図のStraight skeletonによる近似

今井敏行 （Part： Lead author )

日本応用数理学会2009年度年会講演予稿集     2009.09

Delaunay図から拡張flipにより生成される三角形分割

今井敏行

日本応用数理学会2008年度年会講演予稿集     2008.09

Delaunay図のflip型構成の一般化

今井敏行

日本応用数理学会2007年度年会講演予稿集     242 - 243   2007

円のVoronoi図のflipによる位相的構成

日本応用数理学会2006年度年会講演予稿集     206 - 207   2006

How to Confirm that a Planar Graph is a Voronoi Diagram for Convex Objects

IMAI Toshiyuki

IPSJ SIG Notes ( Information Processing Society of Japan (IPSJ) )  99 ( 5 ) 15 - 22   2005.01

　View Summary

In Geometric processing, implementations of approximated algorithms or those of exact algorithms with numerical errors do not guarantee the the correctness of the output. For the construction of Voronoi diagrams for points, a theorem related to the Delaunay diagram, which is the dual of the Voronoi diagram for points, gives us a local test to confirm that the output is the correct Voronoi diagram. In this paper, the theorem is extended to apply to the construction of the Voronoi diagrams for convex objects and the proof is given. This theorem allows us to obtain the correct Voronoi diagram for some convex objects by using an approximated algorithm.

A Method for Determining the Topological Structure of Voronoi Diagram for Segments by Using Voronoi Diagram for Points

WATANABE Hideomi, IMAI Toshiyuki

IPSJ SIG Notes ( Information Processing Society of Japan (IPSJ) )  99 ( 5 ) 7 - 14   2005.01

　View Summary

An approximate Voronoi diagram for segments can be constructed from the Voronoi diagram for points by replacing each segments with some points. There is no algorithm for approximate construction which guarantees that the topological structure of approximated diagram is exactly the same as the original Voronoi diagram for segments. This paper describes how to determine the topological structure of a Voronoi diagram for segments from the approximated one. First, all segments are replaced with the endpoints to construct the initial approximate Voronoi diagram for the endpoints and then the diagram is modified by adding internal points of the segments in certain manner until it is judged that the approximate diagram has the same topological structure as the original Voronoi diagram only by investigating Voronoi edges of the approximated diagram.

点Voronoi図による線分Voronoi図の位相的に正しい近似構成法

今井敏行 （Part： Lead author )

日本応用数理学会2005年度年会講演予稿集   206-207   2005

一般化Voronoi図の一貫性と局所フリップ不可能性について

日本応用数理学会2004年度年会講演予稿集   452-453   2004

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

今井 敏行

情報処理学会研究報告. 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.

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