入力誤差を反映した凸包問題とその解法(計算量理論とアルゴリズム論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
計算幾何学の分野ではアルゴリズムをプログラムとして実装する際に障害となる計算誤差・入力誤差の取扱いについて従来からさまざまな研究が行われており, 基本的な問題である凸包問題についても計算誤差を考慮したアルゴリズムが多数知られている.しかしながら, 入力誤差が存在する場合の凸包問題ついてはほとんど研究が行われていない.本論文では入力誤差が存在する場合の凸包問題について考察を行い, 出力の凸包を「入力誤差の影響を受ける部分」と「入力誤差の影響を受けない部分」に分割するという手法を提案する.提案する手法では入力誤差の影響を受けない領域として「入力の表すすべての凸包に対して常に内部/外部にある領域(それぞれを内部信頼領域/外部信頼領域と呼ぶ)」を構成する.入力の各点に対して誤差の大きさが与えられているという仮定のもとでこれらの領域を構成するアルゴリズムについて考察を行った結果, n個の入力点に対してO(n log n)時間で外部信頼領域を構成するアルゴリズム, 最適時O(n log n), 最悪時O(n^3時間で内部信頼領域を構成するアルゴリズムがそれぞれ得られた.
- 1998-06-25
著者
-
永井 孝幸
鳥取環境大学環境情報学部情報システム学科
-
都倉 信樹
大阪大学基礎工学部情報工学科
-
都倉 信樹
大阪大学大学院基礎工学研究科
-
安留 誠吾
南大阪大学
-
永井 孝幸
大阪大学大学院基礎工学研究科情報数理系専攻
-
安留 誠吾
大阪大学大学情報処理教育センター
-
安留 誠吾
大阪工業大学情報科学部
関連論文
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- 入力誤差を反映したボロノイ領域(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 個人所有ノートPCを用いた計算機環境(セッション2)
- 「アクレディテーション」
- ユーザのアクセスコストを最小化するハイパーテキストの構成法
- 大きい目標の選択操作に対するFittsの法則の適合性
- アクセスコストを最小化するハイパーテキストの構成法
- アクセスコストを最小化するハイパーテキストの構成法
- 実験環境と実使用環境における目標選択動作の比較
- 大きい目標の選択操作に対するFittsの法則の適合性の評価
- 最適メニュー階層構造を求めるアルゴリズムについて
- 最適メニューシステムの設計法について
- 最適なメニュー階層構造を求めるアルゴリズム
- Fittsの法則に基くマウスの操作方向の効率への影響
- 5X-6 情報教育のための教育基本ソフトウェア・電子教材・教育支援プロジェクト
- 衝突検出機構のないマルチアクセスチャネルでの自己安定リーダ選択アルゴリズム(計算量理論とアルゴリズム論文小特集)
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム(並列・分散)
- マルチアクセスチャネルを利用した自己安定リーダ選択アルゴリズムの改良
- マルチアクセスチャネルを利用した自己安定リーグ選択アルゴリズム
- 分散システムにおける大域条件式成立の可能性検出
- 移動ネットワークを含む分散システムとその上のスナップシヨット・アルゴリズム
- マルチアクセスチャネル上での自己安定リーダ選択アルゴリズム
- 拡張されたヒープ領域管理機能をもつPASCAL処理系ELPH
- PASCALシンボリック・デバッガの作成
- 「JABEEの発足と情報処理学会アクレディテーション委員会活動」
- 再構成アレー上の接頭部和問題について
- 再構成アレイ上で接頭部和を求めるアルゴリズムについて
- ミニコンピュータ複合体とそのオペレーティング・システム
- マウスとペンの操作精度の比較
- 情報教育に何が一番必要か
- 学生が作業スタッフとして参加する学科内全科目の講義撮影・配信への取り組み
- 日常運用可能な省力型ビデオアーカイブシステムの構築 : ハンディカムによる全講義有人収録方式との連携(新しいインターネット技術の教育環境への利用/一般)
- 鳥取環境大学次期授業支援システムの開発
- 7-104 学科内全講義のビデオ撮影・蓄積・配信への取り組み((9)e-ラーニング実践-I)
- 教員の作業効率向上を目指した授業支援システムの構築と運用
- (225)遠隔ペアプログラミング支援システムSATORIの開発とプログラミング教育への適用(セッション64 e-ラーニング(インターネット・マルチメディア利用教育を含む)V)
- (135)教員の作業効率向上を目指した授業支援システムの構築と運用(セッション39 教育システムA(講義・演習)IX)
- (96)大学内でのアンケートシステムの運用事例と考察(セッション28 教育評価・自己点検・評価システムIV)
- 6.必携パソコン化編(2.教育用計算機環境の事例)(大規模分散ネットワーク環境における教育用計算機システム)
- 学生による講義ビデオのしおり付け実験の報告
- 授業内の学生の反応を記録・解析するシステムの運用報告
- 精度保証された反復反射計算の実装法
- (148)Javaを導入言語としたプログラミング教育(第39セッション 教育研究指導(III))
- (134)鳥取環境大学における学生ノートPCを活用した情報処理教育(第36セッション 教育システム(講義・演習)(VII),教材の開発)
- (52)情報数学導入科目の一つの構想と実施経験(第14セッション 教材の開発(II))
- (15)生徒と教師の授業時間内のやりとりを支援するシステムの実装と評価(第4セッション 教育システム(講義・演習)(IV))
- 合同な点クラスタに対する点クラスタボロノイ図の構成
- 入力誤差を反映したボロノイ領域
- 入力誤差を反映した凸包問題とその解法(計算量理論とアルゴリズム論文小特集)
- 入力誤差を考慮した凸包問題
- 入力が誤差を含む場合の厳密な交差判定
- 計算機演習室におけるGUI操作履歴の収集と解析
- GUIにおける実操作履歴の取得とその意図分析
- 2本の平行線間へのチェインの配置問題
- 入力誤差をAffine Arithmeticで表現した交差判定問題
- 2本の平行線間へのチェインの配置問題
- 多角形内での2-リンクアームの到達可能性判定問題
- 点集合の移動に関する最短経路問題について
- 障害物のある平面上で水平線分に制限をおいた水平垂直線分からなる最短経路について
- 障害物の重みを考慮した最短経路問題
- 計算機構造の教育支援システム
- 凸包問題を解く最適並列アルゴリズム
- コーダルリング上における分散リーダ選択問題の通信計算量とリンク長のトレードオフ
- 二つの凸多角形の重なりを求める最適な並列アルゴリズム
- 演習内に複数の教室で授業情報を共有し蓄積できる教員用システムの開発と運用(ヒューマンインタフェース技術の教育への利用/一般)
- 高等学校教育におけるポートフォリオシステムの研究(認知と学習・教育用インタフェース/一般)
- 大学教育に適した学生ポートフォリオシステム
- 生徒と教師の協調学習授業を支援するインタラクティブなシステムの実現
- ウィンドウシステム間の違いを吸収するライブラリの実現について
- プログラミング教育を目的としたチャート型言語システム
- アルゴリズム教育を目的としたチャート型言語システム
- ユーザインタフェース作成支援システムの設計と試作について
- 離散周波数制御を利用した2次電池の最長利用のためのタスクスケジューリングアルゴリズム
- 実行順序制約を有するタスク群における2次電池の最長利用のためのスケジューリングアルゴリズム
- 携帯機器の2次電池の最長利用を目的とするリアルタイムスケジューリングアルゴリズム
- 離散周波数制御を利用した消費電力最小のタスクスケジューリングアルゴリズム
- 2次電池の最長利用を目的としたリアルタイムスケジューリングアルゴリズム
- (84)ある創成科目の計画立案と実施状況 : 2年生向け創成科目の事例(第21セッション 創成教育(I))
- PDP-11/20デュアルシステムにおけるデバイスシェアリングシステムの製作
- 情報処理専門教育について 大学等における情報系専門教育の改善への提言
- 言語Cのライブラリ形式によるコンカレント機能の実現
- 分散型システム記述用言語Concurrent Cの設計とその処理系の実現
- 相互排除問題を解く均一な自己安定分散アルゴリズム
- 異種並列計算環境におけるブロードキャストスケジューリング(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- 異種クラスタシステムにおけるブロードキャストスケジューリングについて
- ヒストリーグラフを用いたアンドゥ機構の提案と評価
- ヒストリーグラフを用いたアンドゥ機構の提案と評価
- マウスドライバの改良によるポインティング精度改善について (ヒューマンインタフェースとインタラクション)
- 日常時と実験時のマウス操作の比較
- (93) ミニレポートへのコメント集と学生の反応(第24セッション マルチメディアの利用(4))
- ポインティング精度向上のためのマウスドライバの改良
- 打鍵レベルでの計算機演習室内の操作履歴の解析と実験データとの比較
- 打鍵レベルでの計算機演習室内の操作履歴の解析と実験データとの比較
- WWW上の正規表現・有限オートマトンの自習・採点支援ツール
- 実験環境との比較によるマウスの日常操作履歴の解析
- 共有メモリシステム上でスナップショット問題を解く分散アルゴリズム
- 超立方体状ネットワークでの最小重み生成木構成分散問題のメッセージ複雑度について
- 完全ネットワークでの最小重み生成木構成分散問題のビット複雑度について