Improvements on Geometric Pattern Matching Problems
Improvements on Geometric Pattern Matching Problems
复制标题
几何图案匹配问题的改进
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
K. Kedem
中科院分区：
文献类型：
--
作者：
L. Paul Chew;K. Kedem
我们考虑以下几何模式匹配问题：找到以 L1 或 L∞ 作为基础度量的平移下两个点集之间的最小豪斯多夫距离。 Huttenlocher、Kedem 和 Sharir 已经证明，可以通过构造某些 Voronoi 曲面的上包络线来找到这个最小距离。此外，他们还表明，如果两个集合的基数均为 n，则此类表面的上包络线的复杂度为 Ω(n3)。我们研究了是否可以绕过这个立方下界的问题，并表明在 L1 和 L∞ 度量下，计算两个点集之间的最小 Hausdorff 距离的时间为 On2 log2n)。
We consider the following geometric pattern matching problem: find the minimum Hausdorff distance between two point sets under translation with L1 or L∞ as the underlying metric. Huttenlocher, Kedem, and Sharir have shown that this minimum distance can be found by constructing the upper envelope of certain Voronoi surfaces. Further, they show that if the two sets are each of cardinality n then the complexity of the upper envelope of such surfaces is Ω(n3). We examine the question of whether one can get around this cubic lower bound, and show that under the L1 and L∞ metrics, the time to compute the minimum Hausdorff distance between two point sets is On2 log2n).