WEKO3
アイテム
アレンジメントと有向マトロイドにおける面列挙アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32702
https://ipsj.ixsq.nii.ac.jp/records/327026d02c3f3-6803-44fe-b450-cf41c0207863
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1989 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1989-10-24 | |||||||
タイトル | ||||||||
タイトル | アレンジメントと有向マトロイドにおける面列挙アルゴリズム | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Combinatorial Face Enumeration in Arrangements and Oriented Matroids | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
筑波大学 | ||||||||
著者所属 | ||||||||
東京工業大学 | ||||||||
著者所属 | ||||||||
東京工業大学 | ||||||||
著者所属 | ||||||||
日本アイ・ビー・エム東京基礎研究所 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Systems Management, the University of Tsukuba | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Sciences, Tokyo Institute of Technology | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Sciences, Tokyo Institute of Technology | ||||||||
著者所属(英) | ||||||||
en | ||||||||
IBM Research, Tokyo Research Laboratory | ||||||||
著者名 |
福田, 公明
× 福田, 公明
|
|||||||
著者名(英) |
Komei, Fukuda
× Komei, Fukuda
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | f_k(F)をd次元アレンジメントFまたはd次元有向マトロイドFのk次元面の数とする。まず面数に関する不等式[numerical formula]を示し、これを用いて有向マトロイドの極大面の集合から全ての面を列挙する多項式時間アルゴリズムを得る。このアルゴリズムは、d次元射影空間やd次元ユークリッド空間内の超平面のアレンジメントにも応用できる。このアルゴリズムとCordovil & Fukudaからアレンジメントの双対グラフから全ての面の位置ベクトルを多項式時間内で再構成することができる。ここで、双対グラフの頂点はこのアレンジメントのd次元面に対応し、二つのd次元面が共通の(d-1)次元面を持つ時対応する二つの頂点が枝で結ばれている。さらに、このアルゴリズムを用いて与えられた(+ 0 -)?ベクトル集合がある有向マトロイドの極大面集合になるかの判定が多項式時間内にできる。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | Let f_k(F) denote the number of k-dimensional faces of a d-arrangement F or a d-dimensional oriented matroid F. It is shown that 〓 for 0〓k〓d. Using the result, we obtain a polynomial algorithm to enumerate all faces from the maximal faces of an oriented matroid. This algorithm can be applied to any arrangement of hyperplanes in P^d or in Euclidean space E^d. Combining this with a result of Cordovil and Fukuda, it is also shown that, given the dual graph of an arrangement (where the vertices are the d-faces and two vertices are adjacent if they intersect in a (d-1)-face), one can reconstruct the location vectors of all faces of the arrangement up to isomorphism in a polynomial time. This in turn enables one to test in a polynomial time whether a given set of (+, 0, -)-vectors is the set of maximal vectors of an oriented matroid. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1989, 号 89(1989-AL-011), p. 1-6, 発行日 1989-10-24 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |