浅野 哲夫 (ASANO, Tetsuo)学長
◆学位
工学士 大阪大学
工学修士 大阪大学
工学博士 大阪大学
◆専門分野
アルゴリズム,特に省メモリ・アルゴリズム,計算幾何学の理論と応用,組み合わせ最適化
◆研究キーワード
アルゴリズム, 計算幾何学の理論と応用, 組み合わせ最適化
◆研究課題
計算幾何学:理論研究
計算幾何学とは,幾何的情報を入力とする計算問題に対する効率的な算法の開発と幾何的計算問題の本質的な計算困難性の解析を目的とする学問分野である。本研究では,計算誤差や入力の縮退のような実用上の諸問題を解決する数学的枠組みを与える。また,双対変換を始めとする幾何的変換による効率化についても考察する。
省メモリ・アルゴリズムに関する研究
メモリが安価になったために大規模な問題を解決したいという要求も高まってきているが,問題規模がメモリ容量よりはるかに速く増大するために作業領域の不足が生じている.そこで作業領域が少なくても動作するアルゴリズムの開発が不可欠であるが,理論的な研究を除いて方法論が確立していないのが現状である.本研究室では,様々な基本的な問題に対して小さな作業領域でも効率よく動作する アルゴリズムの開発を行っている.現在までに開発したアルゴリズムは,計算幾何学の基本的な問題(ボロノイ図作成,デローネイ三角形分割構成,ユークリッド最小木構成,多角形内部の最短経路発見)の他,2値画像に関する基本的な諸問題(連結成分の個数のカウント,最大成分で決まる画像の出力,連結成分に応じたラベリング)などについても小さな作業領域で効率よく問題を解くアルゴリズムの開発に成功している.
計算幾何学:応用研究
計算幾何学は一見幾何と無関係に思われる分野にも積極的に応用されているが,本研究では画像処理分野に従来の手法と全く異なる切り口で接近する。与えられた画像を対象物と背景に2分割する問題や,濃淡画像を白黒2値画像で近似する問題(ディジタルハーフトーニング)などを数学的最適化問題として定義し,その計算複雑度を論じるとともに,ある制約の下では効率よく実行できる算法の開発およびその計算機実験を行っている。

■研究業績

◆発表論文
A new algorithmic framework for basic problems on binary images.
Tetsuo Asano,Lilian Buzer,Sergey Bereg
Discrete Applied Mathematics, 216, 376-392, 2017
Reprint of: Memory-constrained algorithms for simple polygons.
Tetsuo Asano,Array,Maike Buchin,Matias Korman,Array,Günter Rote,André Schulz 0001
Comput. Geom., 47, 3, 469-479, 2014/04
(O)over-tilde(root n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
Asano Tetsuo, Kirkpatrick David, Nakagawa Kotaro, Watanabe Osamu
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE, PT II, 8635, 45-56, 2014
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem.
Tetsuo Asano,David G. Kirkpatrick,Kotaro Nakagawa,Osamu Watanabe 0001
Electronic Colloquium on Computational Complexity (ECCC), 21, 71-, 2014
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability.
Tetsuo Asano,David G. Kirkpatrick,Kotaro Nakagawa,Osamu Watanabe 0001
Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, 45-56, 2014
◆Misc
Depth-First Search Using O(n) Bits
Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8889, 553-564, 2014/01/01
Memory-constrained algorithms for shortest path problems
Tetsuo Asano, Benjamin Doerr
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, -, 2011/12/01
Finding nearest larger neighbors A case study in algorithm design and analysis
Tetsuo Asano, Sergey Bereg, David Kirkpatrick
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5760 LNCS, 249-260, 2009/10/16
Distance trisector curves in regular convex distance metrics
Tetsuo Asano, David Kirkpatrick
Proceedings - 3rd International Symposium on Voronoi Diagrams in Science and Engineering 2006, ISVD 2006, 8-17, 2006/12/01
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface
Tetsuo Asano
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4288 LNCS, -, 2006/12/01
◆書籍
アルゴリズムイントロダクション
Cormen Thomas H., Leiserson Charles Eric, Rivest Ronald L., Stein Clifford, 浅野 哲夫, 岩野 和生, 梅尾 博司, 山下 雅史, 和田 幸一, 近代科学社, 9784764904088, 2013
アルゴリズムとデータ構造 : 基礎のツールボックス
Mehlhorn Kurt, Sanders Peter, 浅野 哲夫, シュプリンガージャパン, 丸善出版, 9784621061879, 2012
基礎・ソート・データ構造・数学
Cormen Thomas H., Leiserson Charles Eric, Rivest Ronald L., Stein Clifford, 浅野 哲夫, 岩野 和生, 梅尾 博司, 山下 雅史, 和田 幸一, 近代科学社, 9784764904064, 2012
高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム
Cormen Thomas H., Leiserson Charles Eric, Rivest Ronald L., Stein Clifford, 浅野 哲夫, 岩野 和生, 梅尾 博司, 山下 雅史, 和田 幸一, 近代科学社, 9784764904071, 2012
コンピュータ・ジオメトリ : 計算幾何学 : アルゴリズムと応用
De Berg Mark, Cheong Otfried, Kreveld Marc van, Overmars Mark H., 浅野 哲夫, 近代科学社, 9784764903883, 2010

■学外活動

◆所属学会
電子情報通信学会, 情報処理学会, ACM学会, IEEE学会
◆学術貢献活動
Japan Conference on Computational Geometry and Graphs , 北陸先端科学技術大学院大学情報科学研究科・教授・浅野哲夫 , 2009/11/11 - 2009/11/13 , 金沢文化ホール
International Seminar on Discrete and Computational Geometry , School of Information Science,Professor,Tetsuo Asano , 2007/09/09 - 2007/09/13 , JAIST
International Workshop on Discrete and Computational Geometry , School of Information Science,ProfessorTetsuo Asano , 2009/06/21 - 2009/06/26 , JAIST and Hakusan Seminar House