昨天被一位老师提问了这个问题，一时没有回答上来，后经过一番查找资料，在这里做一下笔记。
问题描述
设有两个有限点集$u_{i}in V_{1} (1leq ileq m)$和$v_{j}in V_{2} (1leq jleq n)$，则两点集中最短距离定义为$d_{min}(V_{1}, V_{2})$=$min$ $d_{u_{i}, v_{j}}$。
问题解法1：穷举求解
直接容易想到的解法，即计算出两点集所有点之间的距离，并寻找最小的那个。伪代码如下：
| Algorithm 1: Brute Force Approach |
|
Input: The node set $V_{1}$ and $V_{2}$ Output: The $d_{min}(V_{1}, V_{2})$ 1. for $i$ =1 to $m$ 2. for $j$ =1 to $n$ 3. Compute the distance between $u_{i}$ and $v_{j}$ 4. end for 5. end for 6. Determine the minimum distance computed along line 1 to line 5 |
易知该算法复杂度为O$(mn)$。这显然不是一个令老师满意的结果，于是考虑一个非穷举的解法。
问题解法2：基于Gabriel图的非穷举解法
经过查找资料，发现文献"Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets"（其PDF的阅读顺序应为从最后一页向上阅读）对此类问题提出了求解方法。原文叙述较简略，本文在此做详细一些的解释。
先对两个点集的并集做Delaunay三角剖分，然后根据Delaunay三角图得到其对偶的Voronoi图；若Delaunay三角图的某条边与其对应的Voronoi图的边交叉，则将其置为Gabriel图的一条边，如此得到Gabriel图；寻找Gabriel图中所有两端点分别属于两不同点集的边，并计算该边的两端点的距离；所有符合条件的距离中最小的那个即为所求。伪代码如下：
| Algorithm 2: Gabriel Graph based Approach |
|
Input: The node set $V_{1}$ and $V_{2}$ Output: The $d_{min}(V_{1}, V_{2})$ 01. Compute the Delaunay triangulation $DT(V)$ of $V=V_{1}cup V_{2}$ 02. Compute the Voronoi diagram $VD(V)$ of $V$ via the Delaunay triangulation 03. if an edge in the $DT(V)$ intersects its corresponding $VD(V)$ edge 04. Put it into the Gabriel graph $GP(V)$ 05. end if 06. for each edge in the $GP(V)$ 07. if its one node $n_{i}in V_{1}$ and another node $n_{j}in V_{2}$ 08. Compute the distance $d_{ij}$ between $n_{i}$ and $n_{j}$ 09. end if 10. end for 11. Determine the minimum distance computed along line 6 to line 10 |
根据该文献，算法复杂度为O$(m+n)log(mn)$，可等价为O$(n)log(n)$，是一种更为高效的算法。当然在$m$和$n$较小时，穷举解法的表现更好。
关于该解法所提到的若干概念，这里给出一些参考链接（不保证原链接的准确性），仅供参考。
- Delaunay三角剖分：可以参考“三角剖分算法(delaunay)”这篇博文；
- Voronoi图：可以参考“泰森多边形（Voronoi图）的matlab绘制”这篇博文；
- Gabriel图：可以参考“Gabriel 图 （gabriel gragh）”这篇博文。
总结
似乎很多中文网页没有特意针对该问题的解法，很多小伙伴也不善阅读英文资料。在此我做一个笔记，也算是这个博客的第一篇文章。
- 还没有人评论，欢迎说说您的想法！
客服
