Google、FB、LinkedIn 面試經驗 - 面試

※ 引述《peter26194 (啦啦哼哈)》之銘言：
: ※ 引述《FRAXIS (喔喔)》之銘言：
: : 我被問過一個問題：在三維空間中有兩個相同大小的圓盤位於不同位置
: : （朝向也可能不同），求這兩圓盤間的最短距離。除了暴力法我還真想
: : 不出來怎麼作..
: 最近也在面試，看到那道題目，試著想了一下解法：
: 給定兩圓c1, c2
: 找出兩圓各自所在的平面p1, p2
: 把兩圓圓心連線得到L線段
: 將L投影到p1上，得到L1線段
: L1的一端點是c1圓心，
: 1)另一端點如果在圓c1之內，那麼此端點就設為a1;
: 2)另一端點如果在圓c1之外，那麼則把a1定為L1和c1的交點
: 用同樣方法，將L投影到p2上，得到L2線段，再找出a2
: 則a1, a2連線就是最短距離
: 靈感是從「平面上的兩圓，要找最短距離，要找圓心連線和兩圓的交點」而來的，
: 我也不太確定這是對的，大家覺得呢？
: (雖然在這裡討論怪怪的，不過應該是可以的吧？)

先釐清一下問題的定義, 確定大家討論的是同一個問題.
圓盤的定義是在某平面上距離圓心小於某半徑的點集合對吧?
如果是兩個圓周找最近點的話問題就簡單得多.

首先先簡化問題. 由於對空間進行旋轉跟平移不影響問題的答案(證明留給讀者),
所以先假設兩圓盤的半徑為 1, 其中一個圓盤位於 XY 平面上,
(i.e. 即圓心為原點 {0, 0, 0} , 法向量平行 Z 軸 {0, 0, 1}),
另一個圓盤圓心向量 C, 法向量 N.
於是這個問題可以寫成求

argmin[A,B](|A - B|),
A · {0, 0, 1} = 0 (1. A 點位於 XY 平面)
|A × {0, 0, 1}| <= 1 (2. A 點限制在半徑 1 的 Z 軸圓柱)
B · N = C · N (3. B 點與 C 共平面, 法向量 N)
|(B - C) × N| <= 1 (4. B 點限制在半徑 1 的 CN 圓柱)

由於條件 1 跟 3 可以簡化一維的自由度, 即已知
Az = 0
Bz = (C · N - BxNx - ByNy) / Nz
問題可簡化為四元二次的 optimization with boundary condition.
當然這樣還是太複雜, 我們必須進一步簡化問題.

一個觀察是, 當兩個圓盤的法向量平行的時候這個問題有 degenerate solution,
可以直接將兩個圓盤投影到任意一個平行平面上,
若有重疊則重疊範圍內的任一對點皆是最短距離.
若無重疊則可選圓心投影連線與兩個圓周的交點.

現在考慮兩個圓盤法向量不平行的情形,
可以證明兩點至少有一個點位於圓周上. 利用歸謬法, 假設兩點皆非位於圓周,
則兩點連線必然與其中一個圓盤的法向量不平行,
因此可以移動該圓盤上的點往連線方向移動而使得連線縮短.
在此我們將問題再次簡化成空間中一圓盤與一圓周求最近兩點. (三元二次最佳化問題.)

現在我們再考慮簡化問題, 求空間中一點與圓盤間最短距離.
這個問題可以寫成簡單函數. 我們再次經由空間變換把圓盤換到以原點為圓心,
法向量平行 Z 軸, 半徑 1, 輸入點為 P.
若 P 點在 XY 平面的投影落在圓內, 則答案為 Pz.
不然則取投影點與圓心連線在圓周上的交點, 即 hypot(hypot(Px, Py)-1, Pz).

Lemma 1: 空間中一點 P 與單位圓盤的最短距離為
f(P) = if hypot(Px, Py) < 1, Pz
else, hypot(hypot(Px, Py)-1, Pz)

回到原問題, 求空間中一圓周與單位圓盤之最短距離, 可以改寫為
argmin[P](f(P))
P · N = C · N
|(P - C) × N| = 1

由於 P 點的自由度只有一維, 其實可以視為一元最佳化問題, 可以經由微分 f 來求極值.

--
その乾いた哀愁の瞳に去來するものは何か？
失ったもの 得たもの
そして廣大なネットの狹間で彼が見たものとは？
虛像と實存と記號の中に彼は今、何を想うのか？

＜バトルプログラマーシラセ＞

--