Question

距离（Distance）

现实问题，考虑两个东西有多相似；化为数学问题，就是考虑两个东西的距离有多接近。

两个数值的距离：用减法、绝对值计算距离。
两个向量的距离：以“ Minkowski Distance ”计算距离。
两串数列的距离：以“ Levenshtein Distance ”计算距离。
　　　　　　　　演算法是“ Dynamic Time Warping ”。
两串字串的距离：字串类似数列，同上。
两串讯号的距离：以“ Linear Predictive Coding ”重新表示讯号，
　　　　　　　　或者以“ Fourier Transform ”重新表示讯号，
　　　　　　　　再用数学公式计算距离。 
两条曲线的距离：以“ Fréchet Distance ”计算距离。
两群点的距离：以“ Hausdorff Distance ”或者“ Matching Distance ”计算距离。
两个集合的距离：以“ Jaccard Index ”或者“ Sørensen–Dice Index ”计算距离。
两棵树的距离：以“ Tree Distance ”计算距离。
两张图的距离：以“ Graph Kernel ”计算距离。

距离函数（Metric）

距离这个词在数学中是有严谨定义的：

一、两个一样的东西，距离等于零，d(A,A) = 0。
二、A 到 B 的距离等于 B 到 A 的距离，d(A,B) = d(B,A)。
三、三角不等式，ABC 三个东西，两边和大于等于第三边，
　　d(A,B) + d(B,C) ≥ d(A,C)
　　d(A,C) + d(B,C) ≥ d(A,B)
　　d(A,B) + d(A,C) ≥ d(B,C)

常见的距离函数：

Euclidean Distance（L₂）：直线距离。
Taxicab Distance（L₁）：垂直、水平移动的距离。
Hamming Distance（L₀）：相对应维度，数值相异的维度个数。

UVa 10508 11085 ICPC 5132

长度（Length）

现实问题，考虑一个东西有多少份量；化为数学问题，就是考虑一个东西的长度是多少。

长度有时候又称为绝对值。

长度函数（Norm）

长度这个词在数学中是有严谨定义的：

一、有些东西长度为零，p(A) = 0。
二、一个东西均匀放大缩小，其长度也随著放大缩小，p(k*A) = |k|*p(A)。
三、两个东西拼装起来，其长度只会短少或保持一样，p(A + B) ≤ p(A) + p(B)。

下面其实用不到长度函数，只是顺便介绍。

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)。