副作用の生じない幾何摂動法の開発

开发不会产生副作用的几何摄动方法

• 批准号: 19650003
• 负责人: 杉原 厚吉
• 金额: $ 2.05万
• 依托单位: Meiji University (2009)The University of Tokyo (2007-2008)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Challenging Exploratory Research
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19650003/
• 关键词: 数理工学; アルゴリズム; 幾何学; 記号摂動; ラゲールドロネーメッシュ; 配線レイアウトチェック; 超摂動; 副作用; 幾何的退化; 摂動; 線分交差検出; 超大規模集積回路; 配線設計; 異常交差; 3次元ドロネー図; メッシュ生成; 体積0四面体; ボロノイ図

本研究の目的は,幾何的退化を解消する従来の記号摂動法が望ましくない副作用をもたらすことを反省し,除きたい退化だけを選択的に解消できる新しい摂動法を開発することである.初年度は,3次元ドロネーメッシュ生成問題を取り上げ,従来の摂動では体積0の四面体が生じるという副作用の防止法を開発した.2年度目は,線分交差判定問題における記号摂動の副作用防止方法を開発し,超大規模集積回路の配線チェックを,例外処理なしで実行できる方法を構築した.最終年度の本年度は,これまでの成果に基づいて,副作用を避けることのできる選択的例外解消法の一般論を追求した.その基本アイデアは,入力データに摂動を加えるという従来の方法をやめて,問題自身に摂動を加えるという発想の転換である.実際に,ドロネーメッシュで体積0の四面体を避けるためには,問題自身をラゲールドロネーメッシュ問題へ置き換え,配線の交差チェックでは,線分をひし形図形に置き換え,いずれの場合も問題自身を変更した.この発想の転換は,データに摂動を加える従来法に対して,「超摂動」とよぶことができる.この新しい考え方を適用することによって,多面体の集合演算における縮退頂点の位相的整合性の確保,コンピュータグラフィックスにおける立体表面模様のすき間解消などの手法を開発できた.これらの研究を通して,「例外は記号摂動によって解消できるからアルゴリズムの設計においては例外は考えなくてもよい」という記述の欺瞞性を告発することもできた.

The purpose of this study is to evaluate the effect of degradation on the side effects of this study. The purpose of this study is to determine the effect of degradation. The purpose of this study is to determine the effect of degradation. At the beginning of the year, the three-dimensional problem generation problem was extracted from the above, and the method to prevent the side effects of the tetrahedron was introduced. 2 in the year 2, the method for the prevention of side effects has been launched, and the method for preventing side effects has been launched, and the method for preventing side effects of wiring in large-scale integrated circuits has been launched. In the most recent year of the year, the results are based on the results, and the side effects are generally pursued by the exception resolution method selected. If you want to do something about it, you will have to do something about it. If you want to do so, you will have to do something about it. In the world, the tetrahedron avoids the problem of the tetrahedron, the problem of the problem itself, the error of the wiring, the shape of the parcel, and the combination of the problem itself. You don't want to do anything about it, you don't want to do it, and you don't want to do it. New methods are used to ensure the integrity of the phase of the polyhedron set calculus, and the solution of the solid surface model is effective. This is an example of a fraudulent notification of fraudulent information.

项目成果

Restricted Edge Contractions in Triangulations of the Sphere with Boundary.

具有边界的球体三角剖分中的限制边收缩。

• 发表时间: 2007
• 作者: Masaki Moriguchi;Kokichi Sugihara
• 通讯作者: Kokichi Sugihara

滑らかな境界を表現する等方的四面体メッシュ生成法

表达平滑边界的各向同性四面体网格生成方法

• 发表时间: 2007
• 期刊: 日本応用数理学会論文誌 17・3
• 作者: 長井超慧;杉原厚吉
• 通讯作者: 杉原厚吉

United States Patent

• 发表时间: 2007
• 作者: Sang H. Choi;Linda H. Hln.kbllnl

Sliver-free perturbation for the Delaunay tetrahedrization

Delaunay 四面体化的无银扰动

• 发表时间: 2007
• 期刊: Computer-Aided Design 39
• 作者: Tetsushi Nishida;Kokichi Sugihara;Masato Kimura;Kokichi Sugihara
• 通讯作者: Kokichi Sugihara

頂点追加による2次元DistMeshの等方性向上

通过添加顶点改善 2D DistMesh 的各向同性

• 发表时间: 2007
• 期刊: 日本応用数理学会論文誌 17・3
• 作者: 長井超慧;杉原厚吉;鈴木宏正
• 通讯作者: 鈴木宏正