Computational Geometry and Discrete Optimization in Architecture and Urban Planning

建筑和城市规划中的计算几何和离散优化

• 批准号: 21300003
• 负责人: KATOH Naoki
• 金额: $ 7.32万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21300003/
• 关键词: アルゴリズム; 組合せ剛性理論; 最速フロー; 最速避難計画; パネルヒンジフレームワーク; 分子剛性予想; Lamanの定理; 組合せ剛性; 避難計画問題; 普遍的最速フロー; 計算幾何学; 剛性理論; 避難計画; 時間拡大ネットワーク; 動的ネットワーク

(1) Molecular framework that models a molecular structure is an important model which is used to predict protein motion. There was a famous open problem called “Molecular conjecture” that deals with the rigidity of molecular frameworks in terms of combinatorial rigidity which was posed more than 25 five years ago. In this project, we could succeed in affirmatively solving this problem.(2) As for the research of dynamic flow network that models the problem of finding an optimal evacuation planning, we developed a polynomial time algorithm that finds a universally quickest flow. Also, we applied our algorithm to evaluate the appropriateness of capacities of evacuation centers in Kyoto City as well as tsunami evacuation buildings in Okisu area of Tokushima Cit y.

（1）模型是一种对蛋白质运动的重要模型。 2）关于找到最佳撤离计划的动态流网络的研究，我们开发了一种多项式时间算法，发现我们的流动最快。作为Tokushima Cit Yi的Okisu地区的海啸撤离建筑物。

项目成果

A Proof of the Molecular Conjecture

• DOI: 10.1007/s00454-011-9348-6
• 发表时间: 2011-06-01
• 期刊: DISCRETE & COMPUTATIONAL GEOMETRY
• 影响因子: 0.8
• 作者: Katoh, Naoki;Tanigawa, Shin-ichi
• 通讯作者: Tanigawa, Shin-ichi

Enumerating Minimally Rigid Body-Hinge Graphs

枚举最小刚体铰链图

• 发表时间: 2012
• 作者: Y.Higashikawa;N.Katoh and Y.Kobayashi
• 通讯作者: N.Katoh and Y.Kobayashi

Resource Allocation Problems, Handbook of Combinatorial Optimization, 2nd edition(D.-Z. Du and P.M. Pardalos Eds.,)

资源分配问题，组合优化手册，第二版（D.-Z. Du 和 P.M. Pardalos Eds.,）

• 发表时间: 2012
• 作者: N. Katoh;Akiyoshi Shioura and T. Ibaraki
• 通讯作者: Akiyoshi Shioura and T. Ibaraki

2.18 最適化する,日本建築学会編 建築・都市計画のための調査・分析方法(改訂版)

2.18 Optimize，日本建筑学会主编，《建筑与城市规划调查分析方法》（修订版）

• 发表时间: 2012
• 作者: S.Kajihara;M.Matsuzono;H.Yamaguchi;Y.Sato;K.Miyase;X.Wen;加藤直樹,瀧澤重志
• 通讯作者: 加藤直樹,瀧澤重志

Constant-time algorithms for sparsity matroids. Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS7391

稀疏拟阵的恒定时间算法。

• DOI: 10.1007/978-3-642-31594-7_42
• 发表时间: 2012
• 期刊: Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)
• 作者: Hiro Ito;Shin-ichi Tanigawa and Yuichi Yoshida
• 通讯作者: Shin-ichi Tanigawa and Yuichi Yoshida