- 著者
-
藤重 悟
牧野 和久
高畑 貴志
柏原 賢二
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.2001, no.7, pp.51-58, 2001-01-19
各辺ベクトルの台の大きさが2以下である多面体のクラスについて考える.このような凸多面体を複基多面体と呼び,頂点をもつ任意の多面体P⊆R^Vについて,次の3つが等価であることを示す.(1) Pが複基多面体である.(2) 台Vの法線ベクトルをもつPの各面は,ある基多面体の反転および軸方向のスケーリングによって得られる.(3) Pの支持関数は,R^Vの各象限上の劣モジュラ関数である.We consider a class of pointed convex polyhedra in R^V whose edge vectors have the support of size at most 2. We call such a convex polyhedron a polybasic polyhedron and show that for a pointed polyhedron P ⊆ R^V the following three statements are equivalent: (1) P is a polybasic polyhedron. (2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes. (3) The support function of P is a submodular function on each orthant of R^V.