Manhattan MST

[kth-competitive-programming]

Manhattan MST

[simonlindholm]

https://github.com/kth-competitive-programming/kactl/blob/master/content/geometry/FastDelaunay.h could do Euclidean MST in O(n log n) (and in practice around 0.4s for n=1e5), but was a bit too long to include in the pdf... now included.

https://gist.github.com/simonlindholm/2867954df2d8a60baa7a92208b64530d is a quad-tree-based Euclidean MST which is shorter (37 lines) but too slow (3s for n=1e5).

[simonlindholm]

Manhattan MST should at least be simple: http://users.eecs.northwestern.edu/~haizhou/publications/zhou02ipl.pdf I suspect we won't get to share code between the two MSTs, however.

[Chillee]

Closed by #138 (oops can only close own issues).