[C++] Efficient Minimum Spanning Tree Construction without Delaunay Triangulation

這 title 是來自一篇 paper [1]，主要是探討如何在 O(n log n) 的時間內找出一顆 minimum spanning tree (MST)。等等，找 MST 這問題不是已經有許多方法可以用 greedy 的技巧在 O(n log n) 做到了嗎? 那這篇發表日期還是在 2001 年的 paper 是有何貢獻呢？原因是這樣的：傳統的 MST 演算法跟這篇要討論的問題其實有一點不同。不同的地方在於傳統 MST 演算法是給一個 undirected graph，要在這 graph 上找一顆 MST；這篇要討論的是給一堆二維座標平面上的點，任兩點間都可以用一條線連起來，要你找出一種連法使得所有的點都被連起來，並且線段總長是最短的。

這個問題其實也有一段時間了，正式的名稱是 Euclidean Minimum Spanning Tree (EMST) [2]。這問題最簡單的做法就是把每個座標點都當成 vertex，先建出一個 complete graph，edge 上的 weight 就是兩點間距離，然後在這個 complete graph 上找 MST 就是答案了。想當然爾，建 complete graph 的時間是 O(n^2)，所以這做法最花時間的地方是建 graph。因此 EMST 的演算法要討論的重點不是 MST，而是怎樣建 graph 最好。

[C++] template value type extraction

各位如果翻開 STL container 的 document，應該會看到有一部分是寫 member type 的 document。其中應該會看到這樣的描述：

value_type : The first template parameter (T)

定義這種 type 其實用途不是為了 container 本身，而是為了使用這個 container 的 user，特別是使用這個 container 的地方是在 template class / function 時，定義這個 type 尤為重要，細節可以參考我之前寫的這篇。然而 C++ template 雖然可以讓程式撰寫上有更好的泛用性，但是因為需要做型態推導上，在使用上只要推導過程中會有疑義都會導致編譯失敗，也因此需要多做些手腳以便能夠順利編譯。這次要講的就是上次那篇 type function 的延伸