2024-03-29T00:47:43Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000317822023-04-27T10:00:04Z01164:02592:02614:02616
最小包含球問題から得られる4-cube グラフの向きづけSmallest Enclosing Ball Orientations of 4-Cube Graphsjpnhttp://id.nii.ac.jp/1001/00031782/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31782&item_no=1&attribute_id=1&file_no=1Copyright (c) 2005 by the Information Processing Society of Japan東京大学大学院情報理工学系研究科コンピュータ科学専攻東京大学大学院情報理工学系研究科コンピュータ科学専攻東京大学大学院情報理工学系研究科コンピュータ科学専攻西鳥羽, 二郎森山, 園子中山裕貴最小包含球問題(SEB) とはアフィン独立な点集合が与えられた時 それらの点を全て境界又は内部に含む半径最小の球を求める問題である. SEBを解くアルゴリズムであるWelzl のアルゴリズムを適用して得られるcube グラフの枝の向きづけをSEB 向きづけという. 本研究では4 点におけるSEB 問題において 与えられた点集合の4 面体のfacet の鈍角三角形の数に着目して場合分けをし 4-cube におけるacyclic なSEB 向きづけの列挙を行い そのHolt-Klee 性を調べた.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.AN1009593X情報処理学会研究報告アルゴリズム(AL)200591(2005-AL-102)43502005-09-162009-06-30