昨天被一位老师提问了这个问题,一时没有回答上来,后经过一番查找资料,在这里做一下笔记。

问题描述

设有两个有限点集$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$较小时,穷举解法的表现更好。

关于该解法所提到的若干概念,这里给出一些参考链接(不保证原链接的准确性),仅供参考。

总结

似乎很多中文网页没有特意针对该问题的解法,很多小伙伴也不善阅读英文资料。在此我做一个笔记,也算是这个博客的第一篇文章。

 

内容来源于网络如有侵权请私信删除