線分の交点列挙問題に対する平面走査法の改良
スポンサーリンク
概要
- 論文の詳細を見る
This paper presents an improvement on the plane sweep algorithm for finding all the intersections of line segments in the plane. Bentley and Ottmann gave an O(N+K)space, O((N+K)longN) time algorithm using the sweep line method where N is the number of line segments and K is the number of intersections. Schorn reduced the arithmetic precision required in the algorithm without increasing the time complexity. However, his algorithm requires additional procedures, which make the algorithm slower. The algorithm proposed in this paper has the same time complexity as the previous ones, but requires less number of computation than Schorn's method and less arithmetic precision than the Bently-Ottmann method. The superiority of the new algorithm is also shown by computational experiments.
- 1998-06-15
著者
関連論文
- 優勢領域に基づいたスポーツチームワークの定量的評価(画像処理,画像パターン認識)
- スポーツビデオデータからの選手の位置検出システム
- ボロノイ図を応用したスポーツチームワークの定量的評価
- 2. 情報科学技術戦略コア(21世紀卓越した情報研究拠点プログラムの目指す研究(前編))
- 情報科学技術戦略コア
- 5-2-1 東京大学「情報科学技術戦略コア」(5-2 情報・電気・電子分野の21世紀COE,3プロジェクトの拠点リーダーより)(5.大学での研究プロジェクト : 21世紀COEプログラム)(グローバル化時代の教育と研究)
- 位相優先分割統治法による3次元凸包の構成(組合せ最適化(1))
- TD-1-3 グラフィックスハードウェアを用いた一般化ボロノイ図の高速描画
- メッシュ生成研究部会活動報告(研究部会だより)
- 頂点追加による2次元DistMeshの等方性向上(実用)
- 領域を単位とする画像内オブジェクト認識
- Unsolved Problems in Robustness of Geometric Algorithms (Computational Geometry and Discrete Mathematics)
- 分かりやすく書こう(寄書)
- 滑らかな境界を表現する等方的四面体メッシュ生成法(実用,メッシュ生成,平成19年研究部連合発表会)
- 「超ロバスト計算原理とモデリング・シミュレーション」特集号に寄せて
- 3枚の2Dシルエット画像からの3D形状設計(セッション1:モデリング,テーマ:CGと記録及びCG一般)
- 北米のメッシュ生成研究の動向 : 第14回メッシュ生成円卓会議に参加して
- Edge CollapseとSizing Functionを用いた等方的メッシュへの簡略化法(メディア表現の創出を支えるモデリングおよびレンダリング手法I)
- 面と線に基づく細分割の拡張(メディア表現の創出を支えるモデリングおよびレンダリング手法I)
- 管材パッキングのシミュレーション(シミュレーションの世界)
- 空間多次元Navier-Stokes方程式に対する無反射境界条件
- PC への入力手段としての実時間ジェスチャ認識のための一手法(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- PC への入力手段としての実時間ジェスチャ認識のための一手法(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- PCへのマルチモーダルな入力手段としてのジェスチャ認識(テーマ関連セッション(3))
- PCへのマルチモーダルな入力手段としてのジェスチャ認識(テーマセッション(3))(CVのためのパターン認識・学習理論の新展開)
- 大域的滑らかさを優先した標高データからの地形復元法の提案
- 幾何アルゴリズム加速のための混合演算に関する研究
- Donald E. Knuth : The TEXbook (20世紀の名著名論)
- 工学から見た数学教育
- Voronoi図に基づく補間法の大域的連続性の向上
- FEM Fast Marching Methodによるボート航行距離の計算
- 応用数理は総合技術
- SSAアルゴリズムを用いた3次元多角形メッシュへの電子透かしの埋め込み
- 流れの中のボロノイ図の近似構成法
- 分割図形のボロノイ図らしさを測る簡便で合理性のある方法の提案
- 最小2乗法によるボロノイ図あてはめ (最適化の数理とアルゴリズム)
- 図形の中心軸の安定した生成法
- 細分割曲面のフィッティングによるメッシュデータの圧縮
- 不規則メッシュ上のG^1連続な補間曲面の生成法
- 直線アレンジメントを構成するための位相優先アルゴリズム
- Crystal Voronoi Diagram and Its Applications (Algorithm Engineering as a New Paradigm)
- 乗法重みつき結晶成長ボロノイ図の近似構成法とその応用(多次元信号処理とその応用・実現論文小特集)
- 2000-NL-138-4 構文情報の定量化とそれを用いた言語比較
- NLC2000-13 構文情報の定量化とそれを用いた言語比較
- Voronoi図を用いた従来より連続性の高い補間公式の構築
- Voronoi図を用いた多次元データの補間 (新しいパラダイムとしてのアルゴリズム工学)
- 不可能立体
- 3次元単体メッシュ生成の課題 : 計算幾何学の立場から (数値計算における前処理の研究)
- ロバストな幾何計算のためのプログラミング技術〔V・完〕 : 位相優先法
- ロバストな幾何計算のためのプログミング技術〔IV〕 : 入力データを無矛盾に!
- ロバストな幾何計算のためのプログラミング技術〔III〕 : 例外のない世界の作り方
- ロバストな幾何計算のためのプログラミング技術〔II〕 : 誤差の生じない世界の作り方
- ロバストは幾何計算のためのプログラミング技術〔I〕 : 幾何計算はなぜ難しいのか
- 線分の交点列挙問題に対する平面走査法の改良
- Voronoi図を用いたもう一つの補間法
- 図形の可逆なミンコフスキー和の提案
- 近似計算による代数的数の符号判定
- ドロネー四面体メッシュの品質改良のための一手法
- 曲線上に配置された母点に対する平均線形時間ボロノイ図構成法
- 3次元ドロネー図の構築における退化に起因する問題点とその対策
- 図形のミンコフスキー和の逆演算は何か
- 一般図形ボロノイ図の近似構成法とその改良
- ロバスト計算 (特集 アルゴリズムの新展開--理論から工学へ)
- 設計モデル理解のためのOMTシミュレータの検討
- 優勢領域図を用いたスポーツチームワークの定量的評価--幾何学的分析によるチームワーク貢献度の定量的評価
- ICIAM2003感想記(ICIAM'03報告)
- (6)不可能物体とイリュージョン(II 論考,建築形態の数理)
- 勢力圏図を利用したスポーツチームワークの解析(スポーツとOR)
- だまし絵の数理 : 人の視覚とロボットの視覚
- 第47回大学入試懇談会報告 : 高等学校数学への期待 : 工学部の立場から
- 数値解析と計算幾何--自動メッシュ生成 (特集 計算幾何の拡がり--情報科学・応用数理・数学にまたがる発展)
- メッシュ生成研究部会発足のお知らせ(部会報告)