最小包含球問題から得られる4-cubeグラフの向きづけ
スポンサーリンク
概要
- 論文の詳細を見る
最小包含球問題(SEB)とはアフィン独立な点集合が与えられた時, それらの点を全て境界又は内部に含む半径最小の球を求める問題である.SEBを解くアルゴリズムであるWelzlのアルゴリズムを適用して得られるcubeグラフの枝の向きづけをSEB向きづけという.本研究では4点におけるSEB問題において, 与えられた点集合の4面体のfacetの鈍角三角形の数に着目して場合分けをし, 4-cubeにおけるacyclicなSEB向きづけの列挙を行い, そのHolt-Klee性を調べた.
- 一般社団法人情報処理学会の論文
- 2005-09-16
著者
-
森山 園子
東京大学ナノ量子情報エレクトロニクス研究機構
-
森山 園子
東京大学大学院 理学系研究科 情報科学専攻 今井浩研究室 修士課程2年
-
中山 裕貴
東京大学大学院情報理工学系研究科
-
西鳥羽 二郎
東京大学大学院情報理工学系研究科コンピュータ科学専攻
-
中山 裕貴
信州大学大学院理工学系研究科
関連論文
- 係数に誤差を持つ多項式同士の整除性判定
- 係数に誤差を含む多項式同士の整除性判定 (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 小さな有向マトロイドの実現可能性の完全な分類
- BDDを用いたグラフのTutte多項式計算の再考察
- 双二次最終多項式による有向マトロイドの実現不可能性判定
- Non-LP orientations, non-line shellings, and non-representable oriented matroids
- Analyzing automorphism groups of oriented matroids by semidefinite programming (Computational Geometry and Discrete Mathematics)
- Computational Analysis of Orientations of Matroids (Computational Geometry and Discrete Mathematics)
- 最小包含球問題から得られる4-cubeグラフの向きづけ
- トーリックイデアルに対する$F_4,F_5$アルゴリズムの解析 (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 計算代数的手法を用いた最小費用流の解析 (グレブナ-基底の理論的有効性と実践的有効性)
- 最小費用流問題の双対問題におけるトーリックイデアルの解析
- 単体的複体のshellability判定
- 4-2 広域交通流シミュレーションによる道路交通騒音予測 : 小布施町を対象として(環境系)
- 三値マトロイドの生成とWhiteの予想に関する実験
- 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
- 40109 小布施町における広域交通流シミュレーションを用いた道路交通騒音予測(環境騒音(2),環境工学I,2012年度大会(東海)学術講演会・建築デザイン発表会)