著者

堀山 貴史

雑誌

情報処理

巻号頁・発行日

vol.53, no.4, pp.418-426, 2012-03-15

---

「任意の凸多面体は,辺を切り開くことで,その面が重ならないように展開することができるだろうか?」これは,計算幾何学の未解決問題の1つである.より正確に言い換えると,「任意の凸多面体は,単純で自己交差のない多角形に辺展開することができるだろうか?」という問いである.展開図と言うと,小学校の算数の時間に,立方体や直方体の箱をチョキチョキと切り開いたのを思い出される方が多いだろう.本稿では,その頃には出てこなかった「単純」や「自己交差」,「辺展開」といった見慣れないキーワードの解説から始め,上記の未解決問題へのアプローチと関連研究について述べる.

著者

堀山 貴史 庄子 亘

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2012, no.9, pp.1-8, 2012-05-07

---

多面体の展開図 (辺展開とも呼ばれる) は,多面体を辺に沿って切り開くことで得られる多角形である.切り開く辺が異なっても,同型な展開図が得られることがある.例えば,立方体には 384 通りの展開の仕方 (つまり辺の切り開き方) があるが,同型なものを除去することで,11 種類の本質的に異なる (非同型な) 展開図が得られる.本稿では,任意の多面体に対し,非同型な展開図の個数を数え上げる方法について述べる.また,この手法をすべての整面凸多面体 (正多面体,半正多面体,ジョンソン・ザルガラーの多面体,アルキメデスの角柱と反角柱) に適用し,それぞれの非同型な展開図の個数を示す.たとえば,角切り二十面体 (サッカーボールフラーレン) には 375,291,866,372,898,816,000 通りの展開方法があるが,同型なものを排除することで 3,127,432,220,939,473,920 種類の異なる展開図が存在することが分かった.An unfolding (also called an edge unfolding) of a polyhedron is a simple polygon obtained by cutting along the edges of the polyhedron and unfolding it into a plane. Different edge-cuts of a polyhedron may have the same (i.e., isomorphic) unfolding. For example, a cube has 384 way of unfolding (i.e., cutting its edges). By omitting mutually isomorphic unfoldings, we have 11 essentially different (i.e., nonisomorphic) unfoldings. In this paper, we propose how to count the number of nonisomorphic unfoldings for any polyhedron. We also give the number of nonisomorphic unfoldings for all regular-faced convex polyhedra (i.e., Platonic solids, Archimedean solids, Johnson-Zalgaller solids, Archimedean prisms, and antiprisms). For examaple, while a truncated icosahedron (a Buckminsterfullerene, or a soccer ball fullerene) has 375,291,866,372,898,816,000 way of unfolding, it has 3,127,432,220,939,473,920 nonisomorphic unfoldings. (This article is a technical report without peer review.)

著者

堀山 貴史 庄子 亘

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2012-AL-140, no.9, pp.1-8, 2012-05-07

---

多面体の展開図 (辺展開とも呼ばれる) は,多面体を辺に沿って切り開くことで得られる多角形である.切り開く辺が異なっても,同型な展開図が得られることがある.例えば,立方体には 384 通りの展開の仕方 (つまり辺の切り開き方) があるが,同型なものを除去することで,11 種類の本質的に異なる (非同型な) 展開図が得られる.本稿では,任意の多面体に対し,非同型な展開図の個数を数え上げる方法について述べる.また,この手法をすべての整面凸多面体 (正多面体,半正多面体,ジョンソン・ザルガラーの多面体,アルキメデスの角柱と反角柱) に適用し,それぞれの非同型な展開図の個数を示す.たとえば,角切り二十面体 (サッカーボールフラーレン) には 375,291,866,372,898,816,000 通りの展開方法があるが,同型なものを排除することで 3,127,432,220,939,473,920 種類の異なる展開図が存在することが分かった.

著者

佐久間 俊慎 小野 廣隆 山下 雅史 朝廣 雄一 牧野 和久 堀山 貴史

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1325, pp.8-14, 2003-05

著者

堀山 貴史 樋口 康介

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.109, no.108, pp.17-21, 2009-06-22

参考文献数

22

---

最長路問題は、各辺に非負整数の距離が与えられた無向グラフに対し、始点s、終点t間のシンプルなパスで、その上の距離の総和が最大となるものを求める問題である。最長路問題は、効率的な多項式時間アルゴリズムが古くから知られている最短路問題とは異なった性質を持つ。例えば、各辺に関連付けられた距離の正負を反転させた最短路問題を解くことで最長路が得られるように一見思われるが、負の閉路(距離の総和が負となる閉路)が存在するため、最短路問題のアルゴリズムを適用することはできない。本研究では、最長路問題、s-t最長路問題、全点対最長路問題を定式化し、全探索および0-1整数計画法に基づく厳密最適化アルゴリズムを提案する。また、JR大都市近郊区間の大回りをベンチマークとして利用し、各手法の実装および評価を与える。

著者

杉本 琢磨 堀山 貴史

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.110, no.232, pp.19-25, 2010-10-08

---

Vickreyオークションでは,第一価格を入札した者が,第二価格で商品を落札する.このオークションは,入札者に対し誘因両立性を持つことが知られている.一方,入札者のプライバシーに配慮して,各入札者の入札額や誰が落札したかを入札者には伏せたまま実行する場合には,競売人が落札者に対して第二価格を偽ることができる.本研究では,秘密分散を用いることで,競売人の不正を許さず,全体の半分未満の参加者がsemi-honestな参加者として結託したとしても情報を漏らさない情報理論的に安全なプロトコルを提案する.このプロトコルは,入札者が直接情報のやり取りを行うことで,第三者機関を必要としないことが特長である.さらに,第一価格入札者が複数存在した場合のタイブレークの方法,オークションの結果が正当であり競売人による不正が無かったことを入札者に納得させる方法を提案する.

著者

土井 伸洋 堀山 貴史 中西 正樹 木村 晋二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM) (ISSN:09196072)

巻号頁・発行日

vol.2004, no.56, pp.41-46, 2004-05-28

---

Cプログラムからのハードウェア合成においてはビット長最適化をはじめとするさまざまなハードウェア向け最適化が必要である.このためにはプログラム中の変数がとりうる値やデータフローを推測することが必要で,静的解析手法が使われることが多いが,精度などの点で不十分な点がある.本稿ではソフトウエア検証の分野で注目されている抽象解釈(Abstract Interpretation)手法に基づくプログラムの解析と,データパス最適化への応用について述べる.Various optimization techniques such as bit-length optimization are required for hardware generation from C programs. The value range analysis and dataflow analysis are effective for such optimization and static pro gram analysis methods have been used. The static methods, however, have several problems such as the preciseness, the overestimation, etc. In this paper, we describe a program analysis method based on abstract interpretation and its application for datapath optimization.