Nearest Neightbor(Under Construction!)

Nearest Neightbor

https://algnotes.wordpress.com/2015/03/12/

ICPC 3270

Relative Nearest Neightbor

http://en.wikipedia.org/wiki/Relative_neighborhood_graph

Gabriel Graph

http://en.wikipedia.org/wiki/Gabriel_graph

α-Shape

http://en.wikipedia.org/wiki/Alpha_shape

β-Skeleton

http://en.wikipedia.org/wiki/Beta_skeleton

Θ-Graph

http://www.cs.tufts.edu/comp/260/lectures.html
http://en.wikipedia.org/wiki/Theta_graph
http://en.wikipedia.org/wiki/Yao_graph

Locality-sensitive Hashing

http://blog.csdn.net/icvpr/article/details/12342159

Farthest Neightbor(Under Construction!)

Farthest Neightbor

求每個點的最遠點。先前介紹的「最遠點對」屬於其中一份子。

Farthest Voronoi Diagram。O(NlogN)。

Farthest Neightbor

查詢的點,不是一開始的點。KD-Tree。

Farthest Neightbor on Convex Hull

無法使用旋轉卡尺。例如一個橢圓。

Randomized Incremental Method。O(NlogN)。

Convex Hull + Monge Matrix。O(N)。

動態問題可以參考這篇,更新、查詢的平均時間複雜度是O((logN)^2)。

http://www.ics.uci.edu/~eppstein/pubs/Epp-CGTA-96.pdf

UVa 12311

Euclidean Geometry(Under Construction!)

Hamilton Circuit

Bitonic Euclidean TSP

ICPC 4791

Taxicab Geometry(Under Construction!)

Taxicab Geometry

L₁ Metric

Closest Pair

ICPC 5848

Farthest Pair

歐氏距離,窮舉法O(N^2),凸包與旋轉卡尺O(NlogN)。

距離公式|x1 - x2| + |y1 - y2| + |z1 - z2|。去掉絕對值,共8種情況。以(x1 - x2) - (y1 - y2) + (z1 - z2)為例,重新整理得到(x1 - y1 + z1) - (x2 - y2 + z2)。若前項盡量大、後項盡量小,則距離越大。

窮舉8種正負號配置情況(因為對稱,其實只需4種)。對於一種情況,窮舉每個點,記錄最大值、最小值。最大值減最小值,即為所求。時間複雜度O(N)。

UVa 11012 Sphere DISTANCE

Mininum Spanning Tree

歐氏距離,Kruskal's Algorithm O(ElogV) = O(NNlogN),其中E = V(V-1)/2 = O(V^2)。Prim's Algorithm O(N^2)。Voronoi Diagram O(NlogN)。

http://blog.csdn.net/acm_cxlove/article/details/8890003

邊數降至4N,可套用Kruskal's Algorithm。O(NlogN)。

ICPC 3662