セッション３: 計算幾何と最適化 (Computational Geometry and Optimization)

計算幾何学はその誕生から30年ほどの間に目覚しい発展をとげ、現在も活発な研究がなされている。計算幾何学と最適化技法とは親密な関係にあり、計算幾何学の問題に対し最適化手法が応用されたり、逆に、最適化技法の中に計算幾何学の手法を持ち込むことで計算効率を大きく改善したりすることがある。本セッションでは計算幾何学の分野で活躍しておられる4名の研究者にご講演いただく。

講演

• 岡本 吉央 （豊橋技術科学大学）
  Yoshio Okamoto (Department of Information and Computer Sciences, Toyohashi University of Technology)
  凸多面体グラフの向き付け：数理とアルゴリズム
  Polytopal Digraphs: Mathematics and Algorithms
  概要 | プロフィール
• 徳山 豪 （東北大学）
  Takeshi Tokuyama (Graduate School of Information Sciences, Tohoku University)
  風変わりなボロノイ図と計算可能性
  Non-standard variations of Voronoi diagrams and related computability problems
  概要 | プロフィール
• 浅野 哲夫 （北陸先端科学技術大学院大学）
  Tetsuo Asano (School of Information Science, JAIST (Japan Advanced Institute of Science and Technology))
  最小２乗法の一般化
  On generalization of a least-squared fitting
  概要 | プロフィール
• 加藤 直樹 （京都大学）
  Naoki Katou (Kyoto University)
  三角形分割とラーマングラフ：建築への応用
  Triangulation and Laman Graph: Application to Architecture
  概要 | プロフィール

概要

岡本 吉央 （豊橋技術科学大学）
Yoshio Okamoto (Department of Information and Computer Sciences, Toyohashi University of Technology)
タイトル： 凸多面体グラフの向き付け：数理とアルゴリズム

Polytopal Digraphs: Mathematics and Algorithms

概要：

線型計画問題，線型相補性問題，双行列ゲームなどに対して，ピボット操作に 基づくアルゴリズムが古くから提案されているが，それらを抽象化することで 凸多面体グラフの向き付けが得られる．本講演では，そのような向き付けに対 して知られていることや考えられている問題を紹介する．

徳山 豪 （東北大学）
Takeshi Tokuyama (Graduate School of Information Sciences, Tohoku University)
タイトル：風変わりなボロノイ図と計算可能性

Non-standard variations of Voronoi diagrams and related computability problems

概要：

ボロノイ図は計算幾何学では基本的なテーマであり、入力点集合の垂直二等分線たちを用いて平面もしくは空間を勢力域に分割する。さまざまなバリエーションが知られているが、本講演では、点集合が敵対関係と協力関係を混合して持ち、中立地帯も有する場合の新しいモデルを不動点定理と関連して紹介を行い、組み合わせ的性質や計算可能性についての議論を行う。浅野哲夫氏とJ. Matousek氏との共同研究をベースにしたものである。

浅野 哲夫 （北陸先端科学技術大学院大学）
Tetsuo Asano (School of Information Science, JAIST (Japan Advanced Institute of Science and Technology))
タイトル：最小２乗法の一般化

On generalization of a least-squared fitting

概要：

最小２乗法というと，実験データの直線当てはめが思い浮かぶが，本講演ではその一般化と，同様の手法の別の問題への応用について述べる． ２次元平面上の点列$(x_1, y_1), (x_2, y_2)< \ldots, x_n, y_n)$として指定される実験データを最も良く近似する直線$y=ax + b$は，この直線との垂直方向距離の差の２乗和$\sum_{i=1}^n ax_i + b - y_i)^2$を最小にする定数$a, b$によって定まる．そのような２つの定数を求めるには，２乗和の式を$a$と$b$を変数と見なして，それぞれで偏微分して$0$と置いて得られる連立方程式を解けばよい．しかし，基準を垂直方向の距離の差（絶対値）の和に変更すると，一般的な偏微分が取れなくなって問題が難しくなる．しかし，計算量的には同じ線形時間で最適な直線が求まることが既に知られている． 本講演では，別の意味での一般化を考える．すなわち，１本の直線で近似するのではなく，任意に与えられた整数$k$に対して，最適な$k$回折れ曲がりの線分列を求めるのである．1回折れ曲がりだけであっても問題は難しいが，多項式時間で解けることを示す．しかも，差の２乗和でも差の絶対値和でも同様に解けることを示す．また，一般の$k$の値に対しては，近似比を幾らでも小さくできる近似アルゴリズムも示す． 直線当てはめ以外の問題にも同じ手法を用いることができる．たとえば，平面上に多数の点が配置されているとして，それぞれの点への距離を指定して，なるべくその距離になるように新たな点を挿入するという問題を考える．実際に配置したときの距離と最初に与えられていた距離との差の（２乗，絶対値）和を最小にするという問題を考えたとき，計算幾何学におけるアレンジメントの概念と併用すると，同じ手法で解けることを示す．

加藤 直樹 （京都大学）
Naoki Katou (Kyoto University)
タイトル：三角形分割とラーマングラフ：建築への応用

Triangulation and Laman Graph: Application to Architecture

概要：

部材がジョイントでつながっているトラス構造物はグラフ構造で表現される。トラス構造物が安定であるための必要最低限の部材から成る場合、静定構造物と呼ばれている。静定構造物に対応するグラフはminimally rigid graphとして知られている。本論文では平面上のトラス構造物を対象として、あたえられた平面上の点集合Ｐに対して、Ｐを頂点とし、辺が交差しないminimally rigid graphをすべて列挙するアルゴリズムについて述べる。minimally rigid graphはLaman graphとも呼ばれ、その組合せ的性質については多くの研究者によって研究されており、そのようなグラフ全体がマトロイドの基を作ることが知られている。したがって、逆探索法によりすべてのLaman graphを列挙することができる。 一方、平面上に埋め込まれた非交差Laman graph全体はマトロイドとはならない。最近、非交差Laman graphに対して、グラフ構造や幾何的構造を明らかにし、非交差Laman graph同士に対して隣接関係を上手に定めることにより逆探索法によって、非交差Laman graphをすべて列挙するアルゴリズムを開発した。あらかじめ用いる枝が一部指定されている場合も取り扱うことができる。本講演ではその概要と構造最適化への応用について述べる。