Research on efficient algorithms for graph structures with geometric properties

具有几何特性的图结构高效算法研究

• 批准号: 23500013
• 负责人: UEHARA Ryuhei
• 金额: $ 3.33万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500013/
• 关键词: アルゴリズム; 計算モデル; グラフ構造; 計算折り紙; グラフ理論; 折紙; 計算幾何; 多面体; 展開図; 幾何表現; 折り紙; 国際情報交流; 計算量; 剛体; 計算幾何学

In this research, I investigate efficient algorithms that solve many problems on geometric graphs. From April 2011 to March 2014, I publish three books (one own book and two translations), 21 journal papers, and 24 presentations at refereed international conferences (two presentations are invited). Especially, I investigate on "computational origami", which is a topic about geometric folding. This area is one of frontiers that have many applications, however, it is not well investigated even in Japan. I propose several remarkable results in this area.

在这项研究中，我调查有效的算法，解决了许多问题的几何图形。从2011年4月到2014年3月，我出版了三本书（一本自己的书和两个翻译），21篇期刊论文，并在国际会议上发表了24篇演讲（两篇演讲被邀请）。特别是，我研究了“计算折纸”，这是一个关于几何折叠的话题。该领域是具有许多应用的前沿领域之一，然而，即使在日本，它也没有得到很好的研究。我建议在这一领域取得若干显著成果。

项目成果

The complexity of the stamp folding problem

邮票折叠问题的复杂性

• DOI: 10.1016/j.tcs.2012.08.006
• 发表时间: 2013
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Takuya Umesato;Toshiki Saitoh;Ryuhei Uehara;Hiro Ito;and Yoshio Okamoto
• 通讯作者: and Yoshio Okamoto

Publications by R. Uehara

R. Uehara 的出版物

The Graph Isomorphism Problem on Geometric graphs

几何图上的图同构问题

• 发表时间: 2013
• 作者: S. Karakawa;E. Morsy;H. Nagamochi;Kazuhiro Furuhashi;R. Uehara
• 通讯作者: R. Uehara

Ghost Chimneys

幽灵烟囱

• DOI: 10.1142/s0218195912500057
• 发表时间: 2012
• 期刊: International Journal of Computational Geometry and Applications
• 作者: D. Charlton;E. D. Demaine;M. L. Demaine;V. Dujmović;P. Morin;and R. Uehara
• 通讯作者: and R. Uehara

Voronoi game on graphs and its complexity

图上的 Voronoi 博弈及其复杂性

• 发表时间: 2011
• 期刊: Journal of Graph Algorithms and Applications
• 作者: S. Teramoto;E. D. Demaine;and R. Uehara
• 通讯作者: and R. Uehara