障害物との交差数が少ない全域木
スポンサーリンク
概要
- 論文の詳細を見る
平面上にn個の点とm個の障害物が与えられたとき、それらの点を張る、直線分を辺とする全域木で、障害物との交差数ができるだけ少ないものを求める問題を考え、次の結果を得た。(i) 障害物が、互いに交差する可能性のある直線分であるとき、交差数がO (min(m^2, m√<n>)) であるような全域木が必ず存在する。(ii) 障害物が、互いに交わらない直線分であるとき、交差数がO (m) であるような全域木が必ず存在する。(iii) 障害物が、互いに交わらない 太った」対象物であるとき 例えば円板) 交差数がO (m+n) であるような全域木が必ず存在する。これらの上界はすべて最適である。
- 一般社団法人情報処理学会の論文
- 1999-05-10
著者
-
玉木 久夫
明治大学理工学部情報科学科
-
浅野 哲夫
北陸先端科学技術大学院大学情報科学研究科
-
Berg Mark
Utrecht University
-
Cheong Otfried
HKUST
-
Guibas Leonidas
Stanford University
-
Snoeyink Jack
UBC
-
浅野 哲夫
Japan Advanced Institute of Science and Technology
-
Berg Mark
Department of Computer Science, Utrecht University
-
Cheong Otfried
Department of Computer Science, Hong Kong University of Science and Technology
-
Guibas Leonidas
Department of Computer Science, Stanford University
-
Snoeyink Jack
Department of Computer Science, University of British Columbia
-
玉木 久夫
Department of Computer Science, Meiji University
-
Cheong Otfried
Department Of Computer Science Hong Kong University Of Science And Technology
-
Tamaki Hisao
The School Of Science And Technology Meiji University
-
Tamaki Hisao
Department Of Computer Science Meiji University
-
Hisao Tamaki
Department Of Computer Science Meiji University.
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- NP-completeness of generalized Kaboozle (コンピュテーション)
- 単純多角形の生成に関する発見的手法(セッション2)
- 眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
- 衝突確率を考慮したバッファ配置問題に対する計算機シミュレーションを利用した手法
- 搬送計画問題に対するネットワーク理論を利用したアプローチ
- より大きな値の最近要素を求める定数作業領域アルゴリズム
- 点集合の距離重複度列のノルムと最大部分集合問題
- 密な部分グラフ問題の貪欲解法
- 放物線のアレンジメントの組合せ複雑度について
- 平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて
- 頂点彩色問題に対する列生成法アプローチの高速化
- テストパターンの静的圧縮における厳密解と貧欲解の比較(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 平面ユークリッドTSPの分割統治法ヒューリスティツクス
- 平面グラフの分枝幅決定アルゴリズムの効率的実装
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- 合成数のAKS witnessに関する実験的研究
- 小さな碁盤における囲碁の厳密解アルゴリズム
- TD-1-12 アルゴリズムデモ発見的動的計画法 : 巡回セールスマン問題を例として
- ハイパーキューブ上の順列の同形を反復しない網羅的生成
- 平面巡回セールスマン問題に対するアローラの近似アルゴリズムの効率的実装
- Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm)
- 障害物との交差数が少ない全域木
- パラメトリックなポリマトロイドとその幾何学的応用
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 巡回カメラマン問題とその自動光学的検査への応用
- 一般化KaboozleのNP完全性
- 制約されたメモリ上での2値画像処理の技法
- 眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
- 眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
- 幾何問題に対する定数作業領域アルゴリズム(1)
- 幾何問題に対する定数作業領域アルゴリズム(2)
- 2値画像上で連結成分を消去するその場でのアルゴリズム
- 正方行列上に一様に整数を配置する方法の提案とディジタルハーフトーニングへの応用
- 正方行列上に一様に整数を配置する方法の提案とディジタルハーフトーニングへの応用
- 教育を目的としたC言語ソース管理APIの作成とその応用(e-learning/一般)
- JavaのeラーニングのためのEclipseプラグインの開発(e-learning/一般)
- 極小横断列挙のメモリ効率の良いアルゴリズム
- 2H-7 耐故障トーラス構成の一方式とシミュレーションによる評価
- 計算幾何学でいかに論文を書くか(学生/教養のページ)
- Constant-work-space algorithms for geometric problems (1) (コンピュテーション)
- Nearest Larger Neighbors問題に対する効率の良いアルゴリズム (理論計算機科学の深化と応用)
- Constant-Working-Space Algorithms (Computational Geometry and Discrete Mathematics)
- 定数の作業領域だけを用いて任意の角度で画像をスキャンする算法
- 直線上に整数点を一様に生成する算法
- 定数作業領域だけを用いたユークリッド距離変換アルゴリズム
- 定数作業領域だけを用いた連結成分ラベル付けアルゴリズム
- 中立地帯を持ったボロノイ図に関する考察
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- ディジタル・ハーフトーニングへの数理工学的アプローチ(OR研究の最前線)
- 精密製造工程における不可視物体の計算幾何学的検知手法
- 復元画像の最適化によるハーフトーン化 : ハードウェアによる高速化を含めた新しい手法
- 適応型クラスタードットハーフトーニング
- 画像処理に対する新たなアプローチ : アルゴリズム研究者の挑戦(招待講演)
- 画像処理 : アルゴリズム工学研究者の視点
- 画像の等高線表現を利用した画像検索手法
- ディジタル・ハーフトーニング : アルゴリズム工学の視点
- 計算幾何学
- 線状ロボットのd_1-最適な移動計画問題の新たな特徴付け
- ディジタル化された領域の周囲長
- 格子充填曲線の存在条件
- LEDA : 複雑なアルゴリズムも簡単にプログラム化できる魔法のツール
- LEDA+アルゴリズム=プログラム (アルゴリズム工学)
- ディジタル直線検出問題の計算量に関するアルゴリズム論的考察(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 計算複雑度から見たディジタルハーフトーニング (新しいパラダイムとしてのアルゴリズム工学)
- Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image
- Voronoi Diagrams with Respect to Criteria on Vision Information
- 単一根有向グラフと対称変換に基づいた囲碁の棋譜管理・閲覧システムの開発(セッション(1) : ゲーム情報学(1))
- 巡回セールスマン問題の近似アルゴリズム:天才アローラによる20年ぶりの急進展(近似アルゴリズムに関する最近の話題)
- 経路最適化問題の近似アルゴリズム : 幾何学的/非幾何学的場合の対比
- ハイパーキューブ上の単距離置換のルーティング
- 組合せ的解析における確率的手法
- Graph Orientation Problems for Multiple st-Reachability
- k-cyclic Orientations of Graphs
- グラフの自動描画における交差を考慮した巨大近傍探索
- 計算幾何学的手法を用いた基本図形の認識
- Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths
- Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
- Approximation Algorithms for Geometric Optimization Problems(Special Issue on Algorithm Engineering : Surveys)
- 最短経路問題に対するメモリ制約付きアルゴリズム
- Computing directed pathwidth in O(1.89n) time
- A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
- Distance Trisector Curveに関する研究の誕生から発展までの経緯
- 任意の作業領域で効率よく線分交差を列挙するアルゴリズム
- A Linear Edge Kernel for Two-Layer Crossing Minimization
- 2値画像の連結成分にラベル付けするための新たな方式
- 既存点までの距離誤差を最小にする点位置発見アルゴリズム
- Search space reduction through commitments in pathwidth computation: an experimental study