# An Energy-Driven Approach to Linkage Unfolding

## プリリミナリー
**Linkage**は辺が硬いグラフ（次数は高々2）．
頂点（節）で自由に向きを変えられる．

Linkageの埋め込み　とは，Linkageの辺の長さの制約を満たすように頂点をユークリッド空間に写像したもの．
辺が交わらないようなもののみをValidな埋め込みとする．

気になっている問題：
Validな埋め込みを連続的に変化させながらUnfoldできるか
Unfold→パスは真っ直ぐになって，サイクルは凸多角形になる．

先行研究：　
4次元以上は広いから余裕
3次元はUnfoldableじゃないケースがある（結び目を考えると良い）
2次元は，必ずUnfoldableなことは知ってる．実際にUnfoldの仕方を計算する研究がいくつかある．→微分方程式を頑張って解くなどで（時間のUpper bound がなかったり，対称性が保たれなかったり，精度が悪かったりする）

今回は多項式時間で終わるし，好きなタイミングの埋め込みを閉形式で得られる．

## 方法
Linkageの埋め込みに対して，エネルギー関数を定義する．
例えば
$E(A) = \sum (||u - v|| + ||u-w|| - ||v-w||) ^ {-2}$
$(v,w)$が辺全体を動き，$u$は(v,w)以外の頂点を動く．

この関数はどういうルールで作ったかと言うと．
- Repulsive 任意の頂点間の距離が増える動きをすると，Eは一次のオーダー減る．
- Separable 連結成分内エナジーと連結成分間エナジーの和でかける．
- Chargeである　辺が交わっている状態と交わってない状態の境目ではEnergyが無限大に発散する
- C^2

### 埋め込みの表現方法は2通りある
- 頂点の座標を指定．→長さの条件が保たれていることが一般には保証されない．$V$
- 次数2の頂点について，角度を指定→長さの条件が保たれている．$Theta$
どちらの場合も，自己交差するかどうかは要チェック

サイクルのとき，外角の和が360度になる必要があるが，その自由度が制限される
→最後の角度を持たない．
→不可能な場合，一通りに定まる場合，二通りになる場合がある

### 最急降下法
$E(Theta)$の最急降下を行うとOK．
収束すれば，outer-convex(unfoldされた状態)というのはわかる．

問題は，どう計算するか．

### ステップ幅を決めるぞ
最急降下法のパラメータといえばステップ幅．
ステップ幅がでかいと，Eが減らなかったりする．
ステップ幅が小さいと終わらなかったりする．

良いステップ幅を見つけましょう．

色んな理由でステップ幅の上界が3つあります．
- $2l_{min}/(n^3l_{max})$
- $D_s/(n^2l_{max})$
- $G/C$

#### $2l_{min}/(n^3l_{max})$
$v_n$を最も外角が大きいものにする．
$n$角形なので，外角は$2\pi/n$以上．
$v_{n-1}, v_1$はある程度近い．
このとき$v_n$以外の情報から$v_n$を補完するとき，$v_n$は凸側か凹側かで二通り考えられる．

このあと，最急降下で$V$が$V'$になったとする．
$||V - V"|| < 2l_{min} / n$ なら 次の$v_n$の場所も補完できる．

ここで，$||V - V'|| < n^2l_{max}||\Theta - \Theta'||$

$||\Theta - \Theta'|| < 2l_{min}/(n^3l_{max})$ ならOKそう．

#### $D_s/(n^2l_{max})$
交わらないでほしい．
$D_s$は初期エネルギー$E(\Theta_0)$以下のエネルギーを持つ埋め込みと，やばい（自己交差を持つ）埋め込みとのユークリッド距離の下界．
ユークリッド空間ではなくて角度空間で議論したいのでうつして，

$||\Theta - \Theta'|| < D_s/(n^2l_{max})$ならOKそう．

#### $G/C$
エネルギーが必ず減ってほしい．

$\Delta t$進んだとしましょう．このときEはどうなるでしょうか．


このとき，$||\nabla E|| > G, ||\nabla^2 E ||< C$とすると，
$\delta t < G/C$ なら$\delta E > \delta t (G / 2)$
になって，$\delta t$を定数にすれば，かならず定数減ることになって嬉しい．
Eは常にPositiveで最初有界なので，有限回で終わることになる．

### Tediousな議論の末，出てくるBounds
Theorem 3. $G \geq d_{min}(\Theta_i) w(\Theta_i)^3 /(5328 n^{8.5} l_{max}^6)$

$w(\Theta) :=$埋め込みの幅．その間にすべての頂点が入るような，２つの平行な直線の距離．
$d_{min}(\Theta) :=$エネルギー関数の分母のやつの最小値．
$l_{max} :=$辺の長さの最大値．

Theorem 4. $C \leq 61920n^6L^7(\Theta_i)/D^{12}(\Theta_i)$

### 最後に $d_{min}(\Theta_i)$ や $w(\Theta_i)$ をおさえる
$d_{min}(\Theta_i) \geq d_{min}(\Theta_0)/n^2$
$w(\Theta_i) > 2d^2_{min}(\Theta_i)/nl_{max}> 2d^2_{min}(\Theta_0)/n^3l_{max}$

$D_s > d_{min}(\Theta_0)/(2n^2)$

## 計算をしましょう
$E(\Theta_0)/(G \Delta t) < X$
Xを計算してください．

$G \geq d_{min}(\Theta_i) w(\Theta_i)^3 /(5328 n^{8.5} l_{max}^6)$
$C \leq 61920n^6L^7(\Theta_i)/D^{12}(\Theta_i)$
$\delta t < G/C$

$X = \Theta(n^69)$

おわり．