WEKO3
アイテム
<i>n</i>次元正軸体を半空間で切り取った際の体積
https://ipsj.ixsq.nii.ac.jp/records/200706
https://ipsj.ixsq.nii.ac.jp/records/200706f24d4f65-7cee-460c-ace5-8caed8839eaa
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL19175018.pdf (686.6 kB)
|
Copyright (c) 2019 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2019-11-21 | |||||||||
| タイトル | ||||||||||
| タイトル | <i>n</i>次元正軸体を半空間で切り取った際の体積 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 専修大学ネットワーク情報学部 | ||||||||||
| 著者所属 | ||||||||||
| 専修大学ネットワーク情報学部 | ||||||||||
| 著者名 |
安藤, 映
× 安藤, 映
× 土屋, 翔一
|
|||||||||
| 著者名(英) |
Ei, Ando
× Ei, Ando
× Shoichi, Tsuchiya
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 本稿では n 次元正軸体を半空間で切り取ってできる多面体の体積を考える．正軸体には指数的に多くの面が存在するため，この多面体の体積は単にシンプレックスに分解する方法では効率的に計算できない．提案アルゴリズムはこの体積を計算するのにO (n6) で実行を完了する．この結果は，0-1 ナップサック多面体の体積を計算する問題が #P-困難であるのと対照的である．本研究でこの体積を計算する動機は，次の問いに肯定的な答えがありうると考えるからである ： もしも幾何双対の関係にある 2 つの多面体の一方に，体積を計算する多項式時間アルゴリズムが存在する場合，もう一方の多面体の体積の計算にも多項式時間アルゴリズムがいつも存在するか？本稿の結果はその予想を真として矛盾はしない例である． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2019-AL-175, 号 18, p. 1-7, 発行日 2019-11-21 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
