最小包含球問題から得られる4-cube グラフの向きづけ

• Item type: SIG Technical Reports(1)
• 公開日: 2005-09-16
• タイトル: 最小包含球問題から得られる4-cube グラフの向きづけ
• タイトル / 言語: en
• タイトル: Smallest Enclosing Ball Orientations of 4-Cube Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院情報理工学系研究科コンピュータ科学専攻
• 著者所属: 東京大学大学院情報理工学系研究科コンピュータ科学専攻
• 著者所属: 東京大学大学院情報理工学系研究科コンピュータ科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer Sciense, Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Computer Sciense, Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Computer Sciense, Graduate School of Information Science and Technology, The University of Tokyo
• 著者名: 西鳥羽, 二郎; 森山, 園子; 中山裕貴
• 著者名(英): Jiro, Nishitoba; SonokoMoriyama; HirokiNakayama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最小包含球問題(SEB) とはアフィン独立な点集合が与えられた時 それらの点を全て境界又は内部に含む半径最小の球を求める問題である. SEBを解くアルゴリズムであるWelzl のアルゴリズムを適用して得られるcube グラフの枝の向きづけをSEB 向きづけという. 本研究では4 点におけるSEB 問題において 与えられた点集合の4 面体のfacet の鈍角三角形の数に着目して場合分けをし 4-cube におけるacyclic なSEB 向きづけの列挙を行い そのHolt-Klee 性を調べた.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Smallest Enclosing Ball(SEB) is the problem which is finding the closed ball of smallest radius that contains given n affinely independent points in (n . 1)-space. The SEB orientations are orientations of cube graphs obtained by applying Welzl’s algorithm to SEB. In this paper, we focus on the number of obtuse triangles in facets of a tetrahedron constructed by 4 given points, and list acyclic SEB orientations of 4-cube. Then we analyze Holt-Klee conditions of such orientations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 91(2005-AL-102), p. 43-50, 発行日 2005-09-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会